# Sum of Lucas Numbers

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?

-
As the question stands, it is not making any sense. Please edit your question to clarify. –  Martin Wanvik Feb 5 '12 at 23:45

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.

• Two sequences are wholly determined by initial conditions. If $\vec{a}=\lambda \vec{b}$ then $a_n=\lambda b_n$ by induction, and the converse holds trivially. Logically, the equivalence of two statements is equivalent to the equivalence of their negations: dependence is the negation of independence.

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.

• Multiply $\alpha^2-\alpha-1=0$ by $\alpha^n$ to get $\alpha^{n+2}=\alpha^{n+1}+\alpha^n$; the same applies to $b_n$. This shows they are both solutions. The vectors $(1,\alpha)$ and $(1,\beta)$ are linearly independent because $\alpha\ne\beta$.

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

-