Question

(1) Let a (.. ,a-2, a-1,ao, a1, a2,...) be a sequence of real numbers so that f(n) an. (We may equivalently write a = (abez) Consider the homogeneous linear recurrence p(A)/(n) = (A2-A-1)/(n) = 0. (a) Show ak-2-ak-ak-1 for all k z. (b) When we let ao 0 and a 1 we arrive at our usual Fibonacci numbers, f However, given the result from (a) we many consider f-k where k0. Using the Principle of Strong Mathematical Induction slow j-,-(-1 n+1 (c) For which values of n do we have f-nfn? (d) Using the Principle of Mathematical Induction, show 2 + (A)2 + + (A)2 for all k E Z20. (Hint: It is much easier to use induction to showr fkfk+1 = ( and then apply (b))

Answer 1

a) From $0=(A^2-A-1)f(n)$ we get

$\begin{align*}0&=A^2f(n)-Af(n)-f(n)\\ &=f(n+2)-f(n+1)-f(n)\\ ~\Rightarrow~~~f(n)&=f(n+2)-f(n+1)\end{align*}$

Put $\begin{align*}n=k-2\end{align*}$ to get $\begin{align*}f(k-2)=f(k)-f(k-1)\end{align*}$ . Thus, $\begin{align*}a_{k-2}=a_k-a_{k-1}\end{align*}$

b) For $\begin{align*}n=0\end{align*}$ we have $\begin{align*}f_{-n}=f_{-0}=f_0=0=-0=-f_0=(-1)^{n+1}f_n \end{align*}$ . Also, for $\begin{align*}n= 1\end{align*}$ we have

$\begin{align*}f_{-n}=f_{-1}=f_1-f_0=1=(-1)^{1+1}f_1 =(-1)^{n+1}f_n \end{align*}$

Suppose that $\begin{align*}n>1\end{align*}$ and that for every $\begin{align*}0 \leq q<n\end{align*}$ it holds that $\begin{align*}f_{-q}=(-1)^{q+1}f_q\end{align*}$ . Then part a) gives

$\begin{align*}f_{-n}&=f_{-(n-2)}-f_{-(n-1)}\\ &=(-1)^{n-1}f_{n-2}-(-1)^nf_{n-1}\\ &=(-1)^{n-1}(f_{n-2}+f_{n-1})\\ &=(-1)^{n-1}f_n \end{align*}$

Thus, by induction, we have $\begin{align*}f_{-q}=(-1)^{q+1}f_q\end{align*}$ for all $\begin{align*}q\geq 0\end{align*}$ .

c) Since $\begin{align*}f_{-q}=(-1)^{q+1}f_q\end{align*}$ , we find

$\begin{align*}f_{-q}&=f_q\\ \mbox{if and only if}\hspace{1.4cm}(-1)^{q+1}f_q&=f_q\\ \mbox{if and only if}\hspace{1.8cm}(-1)^{q+1}&=1\\ \mbox{if and only if}\hspace{3cm}q&=2r-1\end{align*}$

for some $\begin{align*}r\end{align*}$ . That is, $\begin{align*}q\end{align*}$ has to be odd.

d) We show that   $\begin{align*}f_kf_{k+1}= f_0^2+f_1^2 +\cdots+f_k^2\end{align*}$ for $\begin{align*}k\geq 0\end{align*}$ .

If $\begin{align*}k= 0\end{align*}$ then $\begin{align*}f_kf_{k+1}=0\end{align*}$ and $\begin{align*}f_k^2=0\end{align*}$ , thus, the statement $\begin{align*}f_kf_{k+1}= f_0^2+f_1^2 +\cdots+f_k^2\end{align*}$ holds for $\begin{align*}k= 0\end{align*}$ .

Suppose that $\begin{align*}f_kf_{k+1}= f_0^2+f_1^2 +\cdots+f_k^2\end{align*}$ . Then

$\begin{align*}f_{k+1}f_{k+2}&=f_{k+1}(f_k+f_{k+1})\\ &=f_kf_{k+1}+f_{k+1}^2\\ &=(f_0^2+\cdots+f_{k}^2)+f_{k+1}^2\\ &=(f_0^2+\cdots+f_{k}^2+f_{k+1}^2)\end{align*}$

Thus, by induction, we have $\begin{align*}f_kf_{k+1}= f_0^2+f_1^2 +\cdots+f_k^2\end{align*}$ for all $\begin{align*}k\geq 0\end{align*}$ .

Using part b) we get

$\begin{align*}f_{-(k+1)}f_{-k}&=(-1)^{k+2}f_{k+1}(-1)^{k+1}f_k\\ &=(-1)^{2k+3}f_{k+1}f_k\\ &=-f_kf_{k+1}\\ &=-(f_0^2+\cdots+f_{k}^2)\end{align*}$

for all $\begin{align*}k\geq 0\end{align*}$ .