# Proving the closed form of a generating function of the sum of n lucas numbers is equal to the n+2th lucas number

1760887     I've been working on this homework problem for a while now and can't seem to solve it. Let $L_n = L_{n-1} + L_{n-2}$ for $n\ge 2$ where $L_0 = 2$ and $L_1 = 1$

$M_n = 1 + \sum_{i=0}^n{L_i}$ Calculate the first few elements of the sequence $M_n$ to observe a simpler formula relating it to the sequence $L_n$. Prove your conjectural formula by using closed expressions for the generating functions $L(z)$ and $M(z)$ of the sequences $L_n$ and $M_n$.

now I've found $M_n = L_{n+2}$

Defined the closed formula of the generating function of a lucas sequence as    $L(z)=\left(\frac{1}{1- \frac{1+\sqrt5}2z}\right)+\left(\frac{1}{1- \frac{1-\sqrt5}2z}\right)$ but now every time I try to solve $M_n$ I end up with generating functions defined by finite series and I don't know how to find the closed formula of those, any help would be appreciated.

• You are not actually defining anything in the first paragraph. You probably want a "=" somewhere in there. – Tobias Kildetoft Apr 27 '16 at 10:46
• Yeah, you're right, oops. thanks JeanMarie for fixing that up – Daan van Schijndel Apr 27 '16 at 10:50
• In my editing of your formulas, I have interpretated in a "latexacilly correct way" what you had written, but the expression of $L(z)$ is not mathematicaly correct (there must be $z$ somewhere on the RHS) – Jean Marie Apr 27 '16 at 10:51
• You're correct, thanks for pointing it out, sorry for the mistakes, I'm new to this website but that doesn't excuse the errors in definition – Daan van Schijndel Apr 27 '16 at 10:53
• I insist: as there is $z$ in the LHS of $L(z)=...$, one should find $z$ on the RHS . – Jean Marie Apr 27 '16 at 11:54

## 1 Answer

HINT: Take advantage of the convolution hiding in the definition of $M_n$. Let

$$f(z)=\frac1{1-z}=\sum_{n\ge 0}z^n\;;$$

then

$$L(z)f(z)=\sum_{n\ge 0}\left(\sum_{k=0}^nL_k\cdot 1\right)z^n=\sum_{n\ge 0}(M_n-1)z^n=\sum_{n\ge 0}M_nz^n-\sum_{n\ge 0}z^n\;,$$

so

$$\sum_{n\ge 0}M_nz^n=L(z)f(z)+\sum_{n\ge 0}z^n\;.$$

• That makes sense, thank you so much! – Daan van Schijndel Apr 27 '16 at 23:36
• Sorry just a small question. I worked out an expression for M (z) but don't really see how this shows Mn = Mn+2 – Daan van Schijndel Apr 28 '16 at 1:26
• @Daan: Basically you want to show that $M(z)=\sum_{n\ge 0}L_{n+2}z^n$. That’s the case if and only if $$z^2M(z)=L(z)-L_1z-L_0\;,$$ so you want to verify that displayed equation. – Brian M. Scott Apr 28 '16 at 2:00