2
$\begingroup$

How would you expand the analytic function $$\frac{1}{1-z-z^2}$$ to a series of the form $$\sum_{k=0}^\infty a_k z^k \, \, ?$$

$\endgroup$
4
  • 4
    $\begingroup$ Start with partial fractions. $\endgroup$ May 2, 2013 at 17:56
  • 2
    $\begingroup$ i can't get $1-z-z^2$ to factorise? $\endgroup$
    – user53076
    May 2, 2013 at 18:22
  • 1
    $\begingroup$ Sure you can. $z^2+z-1=0$ has the roots $\frac{-1\pm \sqrt{5}}{2}$. Call these $\alpha$ and $\beta$. Then $z^2+z-1=(z-\alpha)(z-\beta)$. $\endgroup$ May 2, 2013 at 18:40
  • $\begingroup$ A related question. $\endgroup$ May 22, 2014 at 15:01

3 Answers 3

13
$\begingroup$

Hint. Consider $$(1-z-z^2)\left(\sum a_kz^k\right)=1$$ as a formal polynomial equation, where the RHS is the polynomial $1=1+0z+0z^2+\dotsb$. Multiplying out the LHS and equating with the RHS term by term, we find that $$\eqalign{a_0\,&=&\;1\cr -a_0+a_1\,&=&\;0\cr -a_0 - a_1 + a_2\,&=&\;0 \cr -a_1 - a_2 + a_3 \,&=&\;0\cr -a_2 - a_3 + a_4 \,&=&\;0 \cr \vdots\;\;\; &&\;\, \vdots\cr}$$ which we can rearrange to $$\eqalign{a_0\,&=&\;1\\a_1\,&=&\;a_0\\a_2\,&=&\;a_0 + a_1\\ a_3\,&=&\;a_1 + a_2\\ a_4\,&=&\;a_2 + a_3 \\ \vdots \;\;&&\;\;\vdots}$$ Does this sequence look familiar$\ldots$?

$\endgroup$
2
  • $\begingroup$ Very nicely done! (+1) $\endgroup$ May 3, 2013 at 2:46
  • $\begingroup$ And using this and the comments in the question, you can get the closed form sequence of fibonacci series. $\endgroup$ May 22, 2014 at 14:17
4
$\begingroup$

Write $1-z-z^2=(a-z)(z+b)$ and and using this, write the partial fraction of $$ \frac 1{1-z-z^2}=\frac 1{a+b}\left(\frac 1 {a-z} +\frac 1 {b+z} \right) $$

$\endgroup$
1
  • $\begingroup$ how do you calculate what $a$ and $b$ are? $\endgroup$
    – user53076
    May 2, 2013 at 18:29
3
$\begingroup$

Three ways:

  • Write as partial fractions: $$ \frac{1}{1 - z - z^2} = \frac{1}{(1 - \tau z) (1 - \overline{\tau} z)} = \frac{\tau}{\sqrt{5} (1 - \tau z)} - \frac{\overline{\tau}}{\sqrt{5} (1 -\overline{\tau} z)} $$ Here $\tau$ is the positive root of $r^2 - r - 1 = 0$, $\overline{\tau}$ the negative one ($\tau$s are zeros of the denominator $1 - z - z^2$). That is: \begin{align} \tau &= \frac{-1 + \sqrt{5}}{2} \\ \overline{\tau} &= \frac{-1 - \sqrt{5}}{2} \end{align} This is a pair of geometric series: $$ [z^n] \frac{1}{1 - z - z^2} = \frac{\tau^{n + 1} - \overline{\tau}^{n + 1}}{\sqrt{5}} $$
  • Expand: \begin{align} \frac{1}{1 - z(1 + z)} &= \sum_{r \ge 0} z^r (1 + z)^r \\ &= \sum_{r \ge 0} z^r \sum_{0 \le s \le r} \binom{r}{s} z^s \\ [z^n] \frac{1}{1 - z - z^2} &= \sum_{r + s = n} \binom{r}{s} \\ &= \sum_{0 \le k \le n} \binom{k}{n - k} \end{align}
  • Recognize the generating function of the Fibonacci numbers: $$ F_0 = 0, F_1 = 1, F_{n + 2} = F_{n + 1} + F_n $$ gives: $$ F(z) = \sum_{n \ge 0} F_n z^n = \frac{z}{1 - z - z^2} $$ so that: $$ \frac{1}{1 - z - z^2} = \frac{F(z) - F_0}{z} = \sum_{n \ge 0} F_{n + 1} z^n $$
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .