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.

  • 1
    $\begingroup$ You are not actually defining anything in the first paragraph. You probably want a "=" somewhere in there. $\endgroup$ – Tobias Kildetoft Apr 27 '16 at 10:46
  • $\begingroup$ Yeah, you're right, oops. thanks JeanMarie for fixing that up $\endgroup$ – Daan van Schijndel Apr 27 '16 at 10:50
  • $\begingroup$ 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) $\endgroup$ – Jean Marie Apr 27 '16 at 10:51
  • $\begingroup$ 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 $\endgroup$ – Daan van Schijndel Apr 27 '16 at 10:53
  • $\begingroup$ I insist: as there is $z$ in the LHS of $L(z)=...$, one should find $z$ on the RHS . $\endgroup$ – Jean Marie Apr 27 '16 at 11:54

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


$$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\;,$$


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

  • $\begingroup$ That makes sense, thank you so much! $\endgroup$ – Daan van Schijndel Apr 27 '16 at 23:36
  • $\begingroup$ Sorry just a small question. I worked out an expression for M (z) but don't really see how this shows Mn = Mn+2 $\endgroup$ – Daan van Schijndel Apr 28 '16 at 1:26
  • $\begingroup$ @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. $\endgroup$ – Brian M. Scott Apr 28 '16 at 2:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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