I would appreciate if somebody could help me with the following problem:
Q: Sequence $\{a_n\}$; satisfy $a_{n+2}=a_{n+1}+a_{n}, a_1=1,a_2=1$
Show by induction:
$$ \frac{a_{2n+4}}{a_{n+2}}=\frac{a_{2n+2}}{a_{n+1}}+\frac{a_{2n}}{a_{n}}$$
I tried induction .But not getting the result!
We are give that $a_{n+2}=a_{n+1}+a_{n}$, $a_1=1$, and $a_2=1$.
Thus, it is easy to see that $a_3=a_2+a_1=1+1=2$, $a_4=a_3+a_2=2+1=3$.
Step 1: Let's use induction on $n$ to show that for $m\ge1$, $n\ge2$, we have
$$a_{n+m}=a_{n}a_{m+1}+a_{n-1}a_{m}$$
For the first benchmark, let $n=2$. Note that $$a_{m+2}=a_{m+1}+a_m=a_{m+1}(1)+a_{m}(1)=a_{m+1}(a_2)+a_m(a_1)$$
So, the identity works for $n=2$.
For the second benchmark, let $n=3$. Note that $$a_{m+3}=a_{m+2}+a_{m+1}=2a_{m+1}+a_m=a_3a_{m+1}+a_2a_m$$
So, the identity works for $n=3$. Let's assume that the identity works for $n$. Then,
$$a_{m+n+1}=a_{m+n}+a_{m+n-1}=(a_{n}a_{m+1}+a_{n-1}a_m)+(a_{n-1}a_{m+1}+a_{n-2}a_m)$$
Collecting terms we have
$$a_{m+n+1}=(a_{n}+a_{n-1})a_{m+1}+(a_{n-1}+a_{n-2})a_m=a_{n+1}a_{m+1}+a_{n}a_{m}$$
and the identity is proven.
Step 2: Here, note that for $m=n$, we have
$$a_{2n}=a_{n+n}=a_{n}a_{n+1}+a_{n-1}a_{n}= a_{n}(a_{n+1}+a_{n-1})$$
Step 3: Now, observe that the term $a_{2n+4}$ can be written $a_{2n+4}=a_{2(n+2)}$. Using the new identity, we see that
$$\frac{a_{2n+4}}{a_{n+2}}=\frac{a_{n+2}(a_{n+3}+a_{n+1})}{a_{n+2}}=a_{n+3}+a_{n+1}$$
$$\frac{a_{2n+2}}{a_{n+1}}=\frac{a_{n+1}(a_{n+2}+a_{n})}{a_{n+1}}=a_{n+2}+a_{n+1}$$
$$\frac{a_{2n}}{a_{n}}=\frac{a_{n}(a_{n+1}+a_{n-1})}{a_{n}}=a_{n+1}+a_{n-1}$$
Finally,
$$\frac{a_{2n+2}}{a_{n+1}}+\frac{a_{2n}}{a_{n}}=\left(a_{n+2}+a_{n+1}\right)+\left(a_{n+1}+a_{n-1}\right)=a_{n+3}+a_{n+1}=\frac{a_{2n+4}}{a_{n+2}}$$
And the proof is complete!