1

Image of problem: http://d2vlcm61l7u1fs.cloudfront.net/media%2F901%2F9010d0fd-aeea-43bb-a993-9327afc7df9e%2FphpiKWhi5.png

Text of problem: $\{a_n\}$ is a sequence of real numbers defined by $a_1=1$, $a_2=2$, $a_3=3$ and $a_n=2a_{n-1} - a_{n-3}$ for $n \geq 4$. Prove that $a_n=a_{n-1} + a_{n-2}$ for every integer $n \geq 3$.

I've gotten this far and I'm not sure where to go from here. Please guide me in the right direction? This is a Strong Principle of Mathematical Induction problem.

We show that $a_{k+1} = a_k + a_{k-1}$. If $k = 2$ then $a_3 = a_2 + a_1 = 3$. Since $a_3 = 3$, it follows that $a_{k+1} = a_k + a_{k-1}$ when $k = 2$. Hence we may assume that $k \geq 2$. Since $k + 1 \geq 3$, it follows that $a_{k+1} = 2a_k - a_{k-2} = 2a_{k-1} + 2a_{k-2} - a_{k-3} - a_{k-4}$.

N. F. Taussig
  • 76,571
Darkdub
  • 365

1 Answers1

1

We do the induction step.

Suppose that we know that for a certain $k$ we have $a_{k-1}=a_{k-2}+a_{k-3}$. We show that $a_k=a_{k-1}+a_{k-2}$.

By the induction hypothesis, $a_{k-1}=a_{k-2}+a_{k-3}$, and therefore $$a_{k-3}=a_{k-1}-a_{k-2}.$$ Thus $$a_k=2a_{k-1}-a_{k-3}=2a_{k-1}-(a_{k-1}-a_{k-2})=a_{k-1}+a_{k-2}.$$

André Nicolas
  • 507,029