I'm having trouble writing the statement of $L_n = \alpha^n + \beta^n \forall n\geq 1$
$\sum_{i=1}^n L_n = \alpha^n + \beta^n$
Any ideas?
I'm having trouble writing the statement of $L_n = \alpha^n + \beta^n \forall n\geq 1$
$\sum_{i=1}^n L_n = \alpha^n + \beta^n$
Any ideas?
Define a recurrence $a_{n+2}=a_{n+1}+a_n$.
Exercise 1: Prove that $a_n$ and $b_n$, both sequences satisfying the recurrence, are linearly independent if and only if their initial condition vectors $(a_0,a_1)$ and $(b_0,b_1)$ are linearly independent.
Exercise 2: Let $\alpha=(1+\sqrt{5})/2$ and $\beta=(1-\sqrt{5})/2$ be the two roots of the characteristic polynomial $x^2-x-1=0$. Show that $a_n=\alpha^n$ and $b_n=\beta^n$ are linearly independent solutions.
E1 proves that the vector space of solutions to the recurrence is two dimensional. E2 provides an explicit basis for this vector space. Hence $L_n=u \alpha^n+v\beta^n$ for some $u,v$. Write the conditions as
$\begin{pmatrix}L_0 \\ L_1 \end{pmatrix} = \begin{pmatrix}1 & 1 \\ \alpha & \beta \end{pmatrix} \begin{pmatrix} u \\ v\end{pmatrix} =\begin{pmatrix} 2 \\ 1\end{pmatrix}. $
Solving this linear system gives $u=v=1$, hence $L_n=\alpha^n+\beta^n$. You may use this in addition to the geometric sum formula to compute $\sum L_k$, and the characteristic polynomial to rearrange further.
Use generating functions. Define $L(z) = \sum_{n \ge 0} L_n z^n$. Multiply your recurrence by $z^n$, add over $n \ge 0$ to get: $ \frac{L(z) - L_0 - L_1 z}{z^2} = \frac{L(z) - L_0}{z} + L(z) $
You have $L_0 = 2$, $L_1 = 1$, so this results in: $ L(z) = \frac{2 - z}{1 - z - z^2} = \frac{1}{1 - \phi z} + \frac{1}{1 - \hat{\phi} z} $ where $1 - z - z^2 = (1 - \phi z) (1 - \hat{\phi} z)$: $ \begin{align*} \phi &= \frac{1 + \sqrt{5}}{2} \\ \hat{\phi} &= \frac{1 - \sqrt{5}}{2} \end{align*} $ The above is just two geometric series: $ L_n = \phi^n + \hat{\phi}^n $ Now, if you really want the sum of Lucas' numbers, the respective generating function is just: $ \frac{L(z)}{1 - z} - \frac{L_0}{1 - z} = -\frac{\phi}{\hat{\phi}} \cdot \frac{1}{1 - \phi z} - \frac{\hat{\phi}}{\phi} \cdot \frac{1}{1 - \hat{\phi} z} - \frac{1}{1 - z} - 2 \frac{1}{1 - z} $ To simplify it somewhat, by Vieta's formulas $\phi \hat{\phi} = -1$, so that: $ \begin{align*} \frac{\phi}{\hat{\phi}} &= - \phi^2 \\ \frac{\hat{\phi}}{\phi} &= -\hat{\phi}^2 \end{align*} $ so: $ \sum_{1 \le k \le n} L_k = \phi^2 \cdot \phi^n + \hat{\phi}^2 \cdot \hat{\phi}^n - 3 = \phi^{n + 2} + \hat{\phi}^{n + 2} - 3 $