Add Me!Close Menu Navigation

Annoying Mclaurin Series

Suppose that we’re given the function B(z) = \frac{1 + z}{1 - z - z^2}, find the ordinary generating function associated with it in the form of B(z) = \sum_{k=0}^\infty b_k k^z. Furthermore, find/compute \sigma_n = \sum_{k=0}^n b_k.

We can employ Taylor’s theorem, but to my knowledge, there’s no easy way to construct the derivatives of B(z) [that’s left to the more ambitious reader ;)] Instead, we focus on classical algebraic techniques to carry us through the day.

Notice that

    \[B(z) = \pa{1+z}\frac{1}{1 - \pa{z\pa{1+z}}},\]

recall that all terms of the form \frac{1}{1-x} = \sum_k x^k, so this becomes

    \begin{align*} B(z) &= \pa{1+z} \underbrace{\sum_{k=0}^\infty z^k (1 + z)^k}_{S(z)} \intertext{let's focus on $S(z)$. Recall that} (1 + z)^k &= \sum_{j = 0}^\infty {k \choose j} z^j \\ S(z) &= \sum_{k=0}^\infty z^k \sum_{j=0}^\infty {k \choose j} z^j \\ \intertext{Let $S_n$ be defined as} S_n &= \sum_{k=0}^n z^k \sum_{j=0}^\infty {k \choose j} z^j \\ S_0 &= 1 \\ S_1 &= S_0 + \pa{{1 \choose 0} z^1 + {1 \choose 1}z^2} \\ S_2 &= S_1 + \pa{{2\choose 0} z^2 + {2\choose 1}z^3 + {2\choose2}z^4} \\ S_3 &= S_2 + \pa{{3\choose0} z^3 + {3\choose1}z^4 + {3\choose2}z^5 + {3\choose3}z^6} \\ \vdots \end{align*}

Okay, let’s suppose that S(z) = \sum_k s_k z^k, then the above tells us that

    \begin{align*} s_0 &= 1 \\ s_1 &= {1\choose0}\\ s_2 &= {2\choose0} + {1\choose1}\\ s_3 &= {3\choose0} + {2\choose1} \\ s_4 &= {4\choose0} + {3\choose1} + {2\choose2} \\ s_k &= \sum_{j=0}^\infty {{k-j}\choose j} \end{align*}

If we compute the first few out, we will see that it looks like

    \[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, \dots\]

Why, this is the Fibonacci sequence! It seems that for the first few terms we looked at, s_k obeys the fibonacci recurrence

    \[s_{k+1} = s_k + s_{k-1} ~~~~ s_{0,1} = 1\]

Lemma (Fibonacci Sequence)

For k \ge 1,

    \[s_{k+1} = s_k + s_{k-1}\]

Proof: Substituting the definition of s_k in, we have

    \begin{align*} s_k + s_{k-1} &= \sum_{j=0}^\infty {k-j \choose j} + {k-j-1\choose j} \\ &= {k\choose 0} + \sum_{j=1}^\infty {k-j \choose j} + {k-j \choose j-1} \\ \intertext{we know that ${a \choose b} + {a \choose b+1} = {a+1\choose b+1}$} &= 1 + \sum_{j=1}^\infty {k-j+1 \choose j} \\ &= \sum_{j=0}^\infty {k-j+1 \choose j} \\ &= s_{k+1} ~~~~ \blacksquare \end{align*}

Finally, recall that B(z) = (1 + z)S(z) = S(z) +zS(z), so

    \[b_k = s_k + s_{k-1} = s_{k+1}\]

so we would expect

    \begin{align*} b_0 &= 1 \\ b_1 &= 2 \\ b_{k+1} &= b_k + b_{k-1} \end{align*}

If we want a closed form, we can find that, letting

    \begin{align*} \psi &= \frac{1 \pm \sqrt{5}}{2} \\ \mu &= \frac{5 \pm 2\sqrt{5}}{5} = \frac{3 + 4\psi}{5} \end{align*}

then

    \[b_k = \frac{\pa{3 + 4\psi_{+}}\psi^{k}_{+} + \pa{3 + 4\psi_{-}}\psi^{k}_{-}}{5}\]

Finally, we can compute \sigma_n = \sum_k b_k

    \[\sigma_n = \pa{3 + 4\psi_{+}}\frac{\psi_{+}^{n+1} - 1}{-\psi_{-}} + \pa{3 + 4\psi_{-}} \frac{1 - \psi_{-}^{n+1}}{\psi_{+}}\]

Posted By Lee

Woosh

  • flood

    heh well that’s an interesting… who would have expected to get fibonacci from that

    and there is a (sorry to say this again) trivially easy way to get the derivatives. it’s just partial fractions and I believe you recover binet’s formula if you add up the taylor expansions of the two fractions.

    • flood

      by the way, try this
      http://mathbin.net/441855

      • http://phailed.me/ Phailure

        I’ll look at this after lunch :P

        You should start a blog/facebook, this trend seems to be heavily one-sided. On the other hand it gives me an (and the only) incentive to post

    • http://phailed.me/ Phailure

      Haha, I feel like you of all people are probably one of the very few that would be allowed to say trivial

    • http://phailed.me/ Phailure

      on the partial function thing, factoring gives B(z) = a/(z + phi) + b/(z + psi) with a + b = 1, aphi+bpsi = 1, and the solution would just be the addition of the [z^n] of a/(z + phi) and b/(z + psi) which is just – (aphi^{1-n} + bpsi^{1-n})

Recent Comments