0

I was solving competitive coding questions, when I read this discussion (via codeforces.com) about efficiently calculating the nth term of a fibonacci series. Here is the relevant comment:

Think about the formula...
$$F_i \;=\; F_{i-1} + F_{i-2} \;=\; 2F_{i-2} + F_{i-3} \;=\; 3F_{i-3}+2F_{i-4} \;=\;\cdots$$ If you keep on with the formula, assuming $F_0 = 1$ and $F_1 = 1$, you'll reach a point where

$$F_i = \begin{cases} (F_{i/2})^2 + (F_{(i/2) - 1})^2 & \text{if $i$ is even}\\[0.5em] F_{\lceil i/2 \rceil} F_{\lfloor i/2 \rfloor} + F_{\lfloor i/2 \rfloor} F_{\lfloor (i/2)\rfloor - 1} & \text{if $i$ is odd} \end{cases}$$

However, I am unable to deduce how he came up with the formula. I did break down the original formula for Fibonacci numbers further but can't see any way to reduce this to $n/2$-th term.

If someone could shed light on this I would be quite thankful.

Blue
  • 75,673
ph0en1x
  • 9
  • 1

1 Answers1

5

Claim. For $n\in\Bbb N$, $$F_{2n}=F_n^2+F_{n-1}^2\qquad\text{and}\qquad F_{2n+1}=F_nF_{n+1}+F_nF_{n-1}. $$

Proof: For $n=1$, $$ F_{2}=2 = 1^1+1^2=F_1^2+F_0^2\qquad\text{and}\qquad F_3=3=1\cdot 2+1\cdot 1=F_1F_2+F_2F_0.$$ For an induction step, $$ \begin{align}F_{2(n+1)}&=F_{2n+1}+F_{2n}\\ &=(F_nF_{n+1}+F_nF_{n-1})+(F_n^2+F_{n-1}^2) \\&= F_nF_{n+1}+(F_n+F_{n-1})F_{n-1}+F_n^2 \\&= F_nF_{n+1}+F_{n+1}F_{n-1}+F_n^2 \\&= (F_n+F_{n-1}F_{n+1}+F_n^2 \\&= F_{n+1}^2+F_n^2 \end{align}$$ and $$\begin{align}F_{2(n+1)+1}&=F_{2(n+1)}+F_{2n+1}\\ &=(F_{n+1}^2+F_n^2)+(F_nF_{n+1}+F_nF_{n-1})\\ &=(F_{n+1}+F_n)F_{n+1}+F_n(F_n+F_{n-1})\\ &=F_{n+2}F_{n+1}+F_nF_{n+1}\\ \end{align} $$ $\square$

Hagen von Eitzen
  • 374,180
  • Thanks for the proof. But isn't induction a non-constructive proof? Meaning we use it to check whether a given formula is correct or not. How can I deduce this particular formula for nth Fibonacci number? – ph0en1x Jul 29 '21 at 11:24