Induction Proof: Formula for Fibonacci Numbers as Odd and Even Piecewise Function How can we prove by induction the following? 
$
  F_{n+1} = \left\{ 
  \begin{array}{l l}
    F_{n/2}^2+F_{(n+2)/2}^2 & \quad \text{if $n$ is even}\\
    F_{(n-1)/2}F_{(n+1)/2}+F_{(n+1)/2}F_{(n+3)/2} & \quad \text{if $n$ is odd }\\
  \end{array} \right.
$
I know that even number is $2m$ and odd number is $2m+1$. 
 A: First, define the Fibonacci numbers: 
Let $F_n$ be the sequence of Fibonacci numbers, given by 
$$F_0 = 0, F_1 = 1, \text{ and}\quad F_n = F_{n-1} + F_{n-2}\; \text{ for}\; n \geq 2.$$ 
Hints:
$(1)$ Use the definition of $F_n$.


*

*E.g., $F_{n+1} = F_{n} + F_{n-1}$


$(2)$ You can use the following good-to-know identities:

i) $F_{n-1}^2 + F_n^2 = F_{2n}$.
ii) $F_{n-1}F_n + F_n F_{n+1} = F_{2n+1}$.

Note that the above identities follow from the more general identity:

$(I)$: For $n, m \in \mathbb{N}$: $$F_{n+m} = F_{n-1}F_m + F_n F_{m+1}$$


Proof of $(I)$:
Fix $n \in \mathbb{N}$. We shall use induction on $m$. For $m=1$, the right-hand side of the equation becomes $$F_{n-1}F_{1} + F_{n}F_{2} = F_{n-1} + F_{n},$$ which is equal to $F_{n+1}$. When $m=2$, the equation is also true.( I hope you can prove this!).
Now assume, that the result is true for $k=3,4, \cdots , m$. We want to show that the result is true for $k=m+1$. $$ \text{For} \ k=m-1 \ \text{we have} \quad F_{n+m-1} = F_{n-1}F_{m-1} + F_{n}F_{m},\,\text{ and}$$ $$ \text{For} \ k = m \ \text{we have} \quad F_{m+n}=F_{n-1}F_{m} + F_{n}F_{m+1}$$ Adding both the sides you will get $$F_{m+n-1} + F_{m+n} = F_{m+n+1} = F_{n-1}F_{m+1} + F_{n}F_{m+2},$$ $$\text{so,}\;\; F_{m+n}=F_{n-1}F_m + F_{n}F_{m+1}$$

Identities (i) and (ii) follow from $(I)$ by putting $m = n$ and manipulating the expressions.

A: Do the following:


*

*Check that it holds for the base case.

*Assume that it holds for all <= 2n (can probably be weakened) .

*You then have that for 2n+1 $$F_{2n+1} = F_{2n}+F_{2n-1} = F^2_n+F^2_{n+1}+F_{n-1}F_{n} +F_nF_{n+1} = F_n(F_n+F_{n-1})+F_{n+1}(F_n+F_{n+1})=F_nF_{n+1}+F_{n+1}F_{n+2}.$$

*Do a similar manipulation for 2n+2 , using what we just proved for 2n+1. You're done. 

