Question

Define a sequence ${⟨a_n⟩}_{n\ge 0}$ by $a_0=0,a_1=1$ and $a_n=2a_{n-1}+a_{n-2}$ , for $n\ge 2$
(a) For every $m>0$ and $0\le j\le m$ , prove that $2a_m$ divides $a_{m+j}+(-1{)}^j{a}_{m-j}$ .
(b) Suppose $2^k$ divides $n$ for some natural numbers $n$ and $k$ . Prove that $2^k$ divides $a_n$ .

Answer 1

(a) Conside $f\left(j\right)=a_{m+j}+(1{)}^j{a}_{mj},0\le j\le m$ , where m is a natural number.
We observe that $f\left(0\right)=2a_m$ is divisible by $2a_m$ .
Similarly,
$f\left(1\right)=a_{m+1}{a}_{m1}=2a_m$
is also divisible by $2a_m$ . Assume that $2a_m$ divides $f\left(j\right)$ for all $0\le j<l$ , where $l\le m$ . We prove that $2a_m$ divides $f\left(l\right)$ . Observe
$f(l-1)=a_{m+l-1}+(-1{)}^{l-1}{a}_{m-l+1}$ ,
$f(l-2)=a_{m+l-2}+(-1{)}^{l-2}{a}_{m-l+2}$ .
Thus we have
$a_{m+l}=2a_{m+l-1}+a_{m+l-2}$
$=2f\left(l1\right)2(1{)}^{l1}{a}_{ml+1}+f(l2\left)\right(1{)}^{l2}{a}_{ml+2}$
$=2f\left(l1\right)+f\left(l2\right)+\left(1{)}^{l1}\right(a_{ml+2}2a_{ml+1})$
$=2f\left(l1\right)+f\left(l2\right)+(1{)}^{l1}{a}_{ml}$ .
This gives
$f\left(l\right)=2f\left(l1\right)+f\left(l2\right)$.
By induction hypothesis $2a_m$ divides $f\left(l1\right)$ and $f\left(l2\right)$.
Hence $2a_m$ divides $f\left(l\right)$.We conclude that $2a_m$ divides $f\left(j\right)$ for $0\le j\le m$ .
(b) We see that $f\left(m\right)=a_{2m}$ . Hence $2a_m$ divides $a_{2m}$ for all natural numbers $m$ . Let $n=2^{k}l$ for some $l\ge 1$ .
Taking $m=2^{k1}l$ , we see that $2a_m$ divides $a_n$ .
Using an easy induction , we conclude that $2^k{a}_l$ divides $a_n$.
In particular $2^k$ divides $a_n$ .