Lucas Numbers Proof $L_n = \alpha^n + \beta^n$

Question

Proof by Induction:

Lucas numbers are recursively defined as: $L_n = L_{n-1} + L_{n-2}$ where $L_1 = 1$ and $ L_2 = 3 $for $n \ge 3$

Show that: $L_n = \alpha^n + \beta^n$ for $\alpha = {1+\sqrt{5}\over2}$ and $\beta = {1-\sqrt{5}\over2}$

Is this the correct approach?

base case:

n = 3

$L_3 = L_2 + L_1 = 4$

$L_3 = \alpha^3 + \beta^3 = 4$

inductive hypothesis:

Assume true: $L_k = L_{k-1} + L_{k-2} = \alpha^k + \beta^k$ for $k\ge3$

inductive step:

$L_{k+1} = L_k + L_{k-1} = \alpha^{k+1} + \beta^{k+1}$

$(\alpha^k + \beta^k) + L_{k-1} = \alpha^{k+1} + \beta^{k+1}$

$L_{k-1} = (\alpha^{k+1} - \alpha^k) + (\beta^{k+1} - \beta^k) = \alpha^{k-1} + \beta^{k-1}$

Answer 1

Our induction assumption is that the formula holds for all $i\le n+1$, and we show that the formula holds for $i=n+2$. So we are using what is called strong induction.

Actually, it is enough to have as induction assumption that the formula holds at $n=k$ and $n=k+1$, and show it holds at $n=k+2$.

So we know that for a certain $k$ we have $L(k)=\alpha^k+\beta^k$ and $L(k+1)=\alpha^{k+1}+\beta^{k+1}$. We show that $L(k+2)=\alpha^{k+2}+\beta^{k+2}$.

By the recurrence, and the induction assumption, we have $$L(k+2)=\alpha^k+\alpha^{k+1}+\beta^k+\beta^{k+1}.$$ But it is easy to verify that $\alpha^k+\alpha^{k+1}=\alpha^{k+2}$, with a similar result for the powers of $\beta$.

Detail: We have $\alpha^2=\alpha+1$, basically by the definition of $\alpha$. Multiply both sides by $\alpha^k$.

Answer 2

Note that for any $\alpha$, $\beta$, $k$, $$(\alpha^k + \beta^k)(\alpha + \beta) = \alpha^{k+1} + \alpha \beta^k + \alpha^k \beta + \beta^{k+1} = \alpha^{k+1} + \beta^{k+1} + \alpha \beta(\alpha^{k-1} + \beta^{k-1}).$$

Now, if $\alpha = (1+\sqrt{5})/2$, $\beta = (1-\sqrt{5})/2$, what are the sum $\alpha + \beta$ and product $\alpha\beta$, respectively?

This should suggest an explicit proof by induction. For the inductive step, we claim that there exists at least one $n$ such that $L_k = \alpha^k + \beta^k$ for all $1 \le k \le n$. Then in particular, $L_n = \alpha^n + \beta^n$ and $L_{n-1} = \alpha^{n-1} + \beta^{n-1}$. But the identity we established above tells us that $L_{n+1} = L_n + L_{n-1} = \alpha^{n+1} + \beta^{n+1}$, completing the inductive step.