2

I have to use generating functions to solve the sum

$$\sum_{k=0}^{m-1} {{k+2} \choose {k}}$$

Now I did this:

$\sum_{k=0}^{m-1} {{k+2} \choose {k}} = \sum_{k=0}^{m} {{k+2} \choose {k}} - {{m+2} \choose m} = \frac{1}{2} ([\sum_{k=0}^{m} {(k+1)(k+2)}] - (m+1)(m+2) )$ then I continued algebrically and got that it is $= \frac{(m+1)(m+2)}{6} = F(m)$

But what is worrying me, is that a solution with the help of Generating functions? I merely used Algebra to solve it, but in the end we get to a generating function.

Or is the way of solving it using generating functions much different?

TheNotMe
  • 4,841
  • I wouldn't do the whole subtraction thing. I'd just define $S_n=\sum_{k=0}^n \binom{k+2}{k}$ and figure out what $S_n$ is, then realize the problem is asking for $S_{m-1}$. – Thomas Andrews May 09 '13 at 15:32

1 Answers1

2

In general if $a_0,a_1,\dots,a_n,\dots$ is a sequence and $s_n=\sum_{k=0}^n a_k$ then if:

$$f(z)=\sum_{n=0}^\infty a_nz^n$$ Then $$\frac{1}{1-z}f(z)=\sum_{n=0}^\infty s_nz^n$$

So, if $a_n=\binom{n+2}{n}=\binom{n+2}{2}$, what is $f(z)$?

Thomas Andrews
  • 177,126
  • To be honest I did not understand what is your point.. – TheNotMe May 09 '13 at 15:18
  • I was just giving you an outline of how you would use generating functions. It depends on what you call "much different." – Thomas Andrews May 09 '13 at 15:30
  • That leads nowhere, the series diverges. – vonbrand May 09 '13 at 15:54
  • 1
    @vonbrand What series diverges? They converge for $|z|<1$ with the $a_n$ proposed. Certainly, $s_n$ doesn't converge as $n\to\infty$, but that isn't the question. – Thomas Andrews May 09 '13 at 16:06
  • I understand that we are looking for $S_n$. And I understand that our generating function we are looking for is $f(x) = \sum_{n=0}^{\infty} {S_n x^n}$. Is that correct? If so, this is a sum of a sum, how do we approach it? – TheNotMe May 12 '13 at 20:36