×

# Prove Using induction

Let, $$<a_n>_{n \ge 0}$$ be a sequence with $$a_0 = 0,a_1=1,$$ and $$a_n=2a_{n-1}+a_{n-2}, \forall n \ge 2.$$ Prove that,for every $$m > 0$$ and $$0\leq j \leq m,2a_m \mid (a_{m+j}+(-1)^j a_{m-j}).$$

Note by Tarit Goswami
2 weeks, 2 days ago

Sort by:

Induct on $$j.$$ For $$j=0,1,$$ $$a_{m+j}+(-1)^j a_{m-j} = 2a_m,$$ so it's clear. Now if $$j \ge 2,$$ write \begin{align} a_{m+j}+(-1)^j a_{m-j} &= 2a_{m+j-1} + a_{m+j-2} + (-1)^j (a_{m-j+2} - 2 a_{m-j+1} ) \\ &= 2\left(a_{m+j-1} - (-1)^j a_{m-(j-1)} \right) + \left( a_{m+j-2} + (-1)^j a_{m-(j-2)} \right) \\ &= 2 \left( a_{m+j-1} + (-1)^{j-1} a_{m-(j-1)} \right) + \left( a_{m+j-2} + (-1)^{j-2} a_{m-(j-2)} \right) \\ \end{align} and both the terms in the parentheses are divisible by $$2a_m,$$ by the inductive hypothesis.

- 1 week, 5 days ago

Are you sure you want that $$2$$ there? I mean, this is never true for $$j=1$$ since $$a_{m+1}+(-1)^1 a_{m-1} = a_m,$$ which is not divisible by $$2a_m.$$

- 1 week, 6 days ago

Yes , it is 2* a_m ..Ooh! sorry there was a typo in recurrence relation i have fixed it .

- 1 week, 5 days ago

×