how to find the formula for $n$-th Fibonacci numbers ($F_n = \frac{a^n-b^n}{a-b}$) and prove it without induction.

Question

The Fibonacci sequence is defined by the recurrence relation $F_{n+2 } =F_{n+1}+ F_n$

A well-known formula for the n-th Fibonacci number is $F_n = \frac{a^n-b^n}{a-b}$ where $a$ and $b$ are the roots for the polynomial $x^2-x-1 $. This formula can be easily proved by induction, as follows: it work for $n =3,2$ and assume it work for $ F_n$ and $ F_{n+1 } $ then $a^{n+2}-a^{n+1}-a^n-b^{n+2}+b^{n+1}+ b^n =0 $ proves it work for $F_{n+2}$ Therefore, by induction, the formula holds for all positive integers $n$. However, this proof does not explain how the formula was discovered or proven in the first place. How did the first mathematician who found this formula come up with it (what is the first proof of this formula )? What are some alternative proofs that do not use induction? who is the first one to discover it ?and how to prove this formula without induction as @user10354138 points out in the comments induction cannot be avoided but what I meant by the question is imagine if you didn't know the formula $F_n = \frac{a^n-b^n}{a-b}$ and you want o find a formula the $n$th term in the sequence how would you it

Answer 1

If the roots of $1-x-x^2$ are $\phi, \psi$, then the generating function can be written as

$$\frac{x}{1-x-x^2} = \frac{x}{(1-\phi x)(1-\psi x)}$$

Use partial fractions to get

$$ = \frac{1}{\phi-\psi}\left[\frac{1}{1-\phi x} -\frac{1}{1-\psi x}\right]$$

Expand both geometric series into

$$ = \frac{1}{\phi-\psi}\left[1+\phi x+(\phi x)^2+\dots - (1+\psi x+(\psi x)^2+\dots)\right]$$

Comparing coefficients with the usual expansion

$$\frac{x}{1-x-x^2} = \sum_{i=0}^\infty F_nx^n $$

gives the result.

Answer 2

Start with $$x^2-x-1=0$$Which can be re-written as $x^2=x+1$. Multiplying both sides by $x$, we get $x^3=x^2+x=2x+1$. Multiplying this expression by $x$ gives $x^4=2x^2+x=3x+2$. Repeating this, we see that $x^n=F_nx+F_{n-1}$. There are two solutions to this equation, which we will denote as $\phi$ and $\phi^*$. So we end up with a system of equations: $$\phi^n=F_n\phi+F_{n-1}$$$$\phi^{*n}=F_n\phi^*+F_{n-1}$$Solving for $F_n$ here is trivial.

Notice here that there was a part where induction is necessary to continue, but this shows how the formula could be discovered. It comes from curiosity (what will happen when we modify the known property of the golden ratio $\phi^2=\phi+1$?) and there is nothing too random in the proof.

Answer 3

If you take as definition $$F_n = F_{n-1} + F_{n-2}, \quad F_0 = 0, \quad F_1 = 1, \tag{1}$$ then the function $$f(n) = \frac{a^n - b^n}{a-b} \tag{2}$$ satisfies $$\begin{align} f(n-1) + f(n-2) &= \frac{a^{n-1} - b^{n-1}}{a-b} + \frac{a^{n-2} - b^{n-2}}{a-b} \\ &= \frac{a^{n-2}(a+1) - b^{n-2}(b+1)}{a-b}. \tag{3} \end{align}$$ If $a, b$ are distinct roots of $x^2 - x - 1 = 0$, then $a^2 - a - 1 = 0$, or $a+1 = a^2$; similarly, $b+1 = b^2$. Consequently $(3)$ becomes $$f(n-1) + f(n-2) = \frac{a^{n-2} a^2 - b^{n-2} b^2}{a-b} = \frac{a^n - b^n}{a-b} = f(n). \tag{4}$$ So we see that $f(n)$ satisfies the recursion property in $(1)$. To see it satisfies the initial conditions, observe that $a, b \ne 0$ and $a \ne b$, so $$f(0) = \frac{a^0 - b^0}{a - b} = \frac{1 - 1}{a - b} = 0, \tag{5}$$ and $$f(1) = \frac{a-b}{a-b} = 1. \tag{6}$$ Therefore, $f(n)$ satsifies the complete definition $(1)$, and $F_n = f(n)$ for all integer $n$.