Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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.

share|cite|improve this answer

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.