3
$\begingroup$

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$.

  • 0
    okay, thanks :D2012-11-28

2 Answers 2

7

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.


  • 0
    yeah i will get back to this in a second, i couldnot solve the problem by now..2012-11-25
1

Do the following:

  1. Check that it holds for the base case.
  2. Assume that it holds for all <= 2n (can probably be weakened) .
  3. 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}.$
  4. Do a similar manipulation for 2n+2 , using what we just proved for 2n+1. You're done.
  • 0
    i am pulling out my hair, can you please explain your logic?2012-11-25