Prove $F_{n-a+1}F_a + F_{n-a}F_{a-1}$

Question

Let $F_n$ denote the nth Fibonacci number, and let $a$ be any integer such that $1 \le a \le n$. Prove that $F_n = F_{n-a+1} F_a + F_{n-a}F_{a-1}$. Pay attention to the base case(s).

Answer 1

Fix $n$ and proceed by induction on $a$. With $F_0 = 0$, $F_1 = 1$, we first consider $a = 1$: $$F_{n-a+1} F_a + F_{n-a} F_{a-1} = F_n F_1 + F_{n-1} F_0 = F_n$$ Now fix some positive integer $k < n$ and assume this holds for $a = k$. We show that this implies it holds for $a = k+1$ also. Begin with the result for $a = k$, $$F_n = F_{n-k+1} F_k + F_{n-k} F_{k-1} \tag{$\star$}$$ Let's consider this term-by-term. By using the defining property of the Fibonacci sequence on $F_{n-k+1}$, we have that $$F_{n-k+1} F_k = \left(F_{n-k} + F_{n-k-1}\right)F_k$$ Similarly on $F_{k-1}$, we have $$F_{n-k}F_{k-1} = F_{n-k} \left(F_{k+1} - F_k\right)$$ Substituting these into our above result, we obtain \begin{align*} F_n &= F_{n-k} F_k + F_{n-k-1} F_k + F_{n-k}F_{k+1} - F_{n-k} F_k \\ &= F_{n-k-1}F_k + F_{n-k}F_{k+1} \\ &= F_{n-k} F_{k+1} + F_{n-k+1}F_k \end{align*} which is precisely the form of ($\star$) with $k \mapsto k + 1$, and hence the result follows by induction.

Answer 2

$F_n$ is the nth Fibonacci number

Simplify $F_{n-a+1}F_{a}+F_{n-a}F{a-1}$

Remember that $F_n = \frac{(\frac{1}{2}+\frac{\sqrt{5}}{2})^n-(\frac{1}{2}-\frac{\sqrt{5}}{2})^n}{\sqrt{5}}$

So that our expression becomes

$(\frac{(\frac{1}{2}+\frac{\sqrt{5}}{2})^{n-a+1}-(\frac{1}{2}-\frac{\sqrt{5}}{2})^{n-a+1}}{\sqrt{5}})\cdot(\frac{(\frac{1}{2}+\frac{\sqrt{5}}{2})^a-(\frac{1}{2}-\frac{\sqrt{5}}{2})^a}{\sqrt{5}}) + ( \frac{(\frac{1}{2}+\frac{\sqrt{5}}{2})^{n-a}-(\frac{1}{2}-\frac{\sqrt{5}}{2})^{n-a}}{\sqrt{5}})\cdot( \frac{(\frac{1}{2}+\frac{\sqrt{5}}{2})^{a-1}-(\frac{1}{2}-\frac{\sqrt{5}}{2})^{a-1}}{\sqrt{5}})$

Expanding

say $\frac{1}{2}+\frac{\sqrt{5}}{2} = x$ and $\frac{1}{2}-\frac{\sqrt{5}}{2} = y$

$(\frac{x^{n-a+1}}{\sqrt{5}}-\frac{y^{n-a+1}}{\sqrt{5}})\cdot(\frac{x^{a}}{\sqrt{5}}-\frac{y^{a}}{\sqrt{5}}) + (\frac{x^{n-a}}{\sqrt{5}}-\frac{y^{n-a}}{\sqrt{5}})\cdot(\frac{x^{a-1}}{\sqrt{5}}-\frac{y^{a-1}}{\sqrt{5}})$

$(1/5)\cdot( x^{n+1}-x^{n-a+1}y^a-x^ay^{n-a+1}+y^{n+1}+x^{n-1}-x^{n-a}y^{a-1}-x^{a-1}y^{n-a}+y^{n-1})$

but $x\cdot{y} = -1$, say $y = -x^{-1}$

$(1/5)\cdot( x^{n+1}-x^{n-a+1}(-x)^{-a}-x^a(-x)^{-n+a-1}+(-x)^{-n-1}+x^{n-1}-x^{n-a}(-x)^{-a+1}-x^{a-1}(-x)^{-n+a}+(-x)^{-n+1})$

$(1/5)\cdot( x^{n+1}-x^{n-2a+1}(-1)^a-x^{-n+2a-1}(-1)^{n-a-1}+x^{-n-1}(-1)^n+x^{n-1}-x^{n-2a+1}(-1)^a-x^{-n+2a-1}(-1)^{n-2a+1}+x^{-n+1}(-1)^n )$