Waste less time on Facebook — follow Brilliant.
×

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

No vote yet
1 vote

Comments

Sort by:

Top Newest

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.

Patrick Corn - 1 week, 5 days ago

Log in to reply

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.\)

Patrick Corn - 1 week, 6 days ago

Log in to reply

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

Tarit Goswami - 1 week, 5 days ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...