Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $f_n$ = $f_{n-1} + n + 6$ where $f_0 = 0$.

I know $f_n = \frac{n^2+13n}{2}$ but I want to pretend I don't know this. How do I correctly turn this into a generating function / derive the closed form?

share|improve this question
4  
For this problem there’s really no need for generating functions at all: by inspection $$f_n=\sum_{k=1}^nk+6n=\frac{n(n+1)}2+6n=\frac{n^2+13n}2\;.$$ –  Brian M. Scott Mar 13 '13 at 14:56
    
+1 that is why I posted two answers. In fact it's harder to find the closed form using generating functions. –  user58512 Mar 13 '13 at 15:24

5 Answers 5

up vote 2 down vote accepted

$$\begin{array}{rcl} G(x) &=& \sum_{n=1}^\infty f_n x^n \\ &=& \sum_{n=1}^\infty (f_{n-1} + n + 6) x^n \\ &=& \sum_{n=1}^\infty f_{n-1} x^n + \sum_{n=1}^\infty n x^ n + \sum_{n=1}^\infty 6 x^n \\ &=& x G(x) + x \frac{d}{dx}\left(\frac{x}{1-x}\right) + 6 \frac{x}{1-x} \end{array}$$

So $$G(x) = \frac{6x^2 - 7x}{x^3 - 3x^2 + 3x - 1} = 7x + 15x^2 + 24x^3 + 34x^4 + 45x^5 + \cdots$$

share|improve this answer
    
Can you explain the last step at all, how you get to 7x + ... etc –  user54089 Mar 13 '13 at 15:11
    
@user54089, long division or use the recurrence relation (or both and check they are the same to make sure you didn't make a mistake). –  user58512 Mar 13 '13 at 15:23
    
How do you get from the generating function to the closed form? –  robjohn Mar 13 '13 at 16:48
    
@robjohn, my comment says "+1 that is why I posted two answers. In fact it's harder to find the closed form using generating functions." I recommend against using generating functions to find the closed form. I have shown how to find the closed form directly from the recurrence in another answer. –  user58512 Mar 13 '13 at 16:49
1  
@caveman: If you are interested, I have derived the general term from the generating function using the appropriate binomial expansions. –  robjohn Mar 13 '13 at 17:23

Here's a way to derive the generating function for $f_n$. Write the recurrence as

$$f_n-f_{n-1}=n+6$$.

The RHS has the following generating function:

$$\sum_{n=1}^{\infty} (n+6) x^n = \frac{x (7-6 x)}{(1-x)^2}$$

Let $f(x)$ be the GF of $f_n$. Then from the above recurrence:

$$f(x) - x f(x) = \sum_{n=0}^{\infty} f_n x^n - \sum_{n=1}^{\infty} f_{n-1} x^n = \frac{x (7-6 x)}{(1-x)^2}$$

because $f_0=0$. Therefore

$$f(x) = \frac{x (7-6 x)}{(1-x)^3}$$

share|improve this answer

$$f_0 = 0,\; f_n = f_{n-1} + n + 6$$

so $$f_{n+1} = \sum_{i=0}^n (i + 6) = T(n) + 6n = \frac{n^2 + 13n}{2}$$

share|improve this answer

Let $$F(x)=\sum_{n=0}^{\infty}f_nx^n=f_0+\sum_{n=1}^{\infty}f_nx^n=\sum_{n=1}^{\infty}(f_{n-1}+n+6)x^n=$$

$$=\sum_{n=1}^{\infty}f_{n-1}x^{n}+\sum_{n=1}^{\infty}nx^n+\sum_{n=1}^{\infty}6x^n=$$

$$=x\sum_{n=1}^{\infty}f_{n-1}x^{n-1}+x\sum_{n=1}^{\infty}nx^{n-1}+x\sum_{n=1}^{\infty}6x^{n-1}=$$

$$=xF(x)+x\frac{1}{(1-x)^2}+6x\frac{1}{1-x}$$ Generating function is $$F(x)=\frac{x+6x(1-x)}{(1-x)^3}=\frac{7x-6x^2}{(1-x)^3}$$

share|improve this answer
    
What is wrong there. Why downvote –  Adi Dani Mar 13 '13 at 15:52
    
because it's exactly the same argument as my answer –  user58512 Mar 13 '13 at 15:56
    
it's a good answer but it's been written already –  user58512 Mar 13 '13 at 15:58
    
my answer is independent and is more explicit then your –  Adi Dani Mar 13 '13 at 16:00
2  
Please move this discussion to meta. –  Mariano Suárez-Alvarez Mar 13 '13 at 16:33

In two answers, it is derived that the generating function is $$ \begin{align} \frac{7x-6x^2}{(1-x)^3} &=x\left(\frac1{(1-x)^3}+\frac6{(1-x)^2}\right)\\ &=\sum_{k=0}^\infty(-1)^k\binom{-3}{k}x^{k+1}+6\sum_{k=0}^\infty(-1)^k\binom{-2}{k}x^{k+1}\\ &=\sum_{k=1}^\infty(-1)^{k-1}\left(\binom{-3}{k-1}+6\binom{-2}{k-1}\right)x^k\\ &=\sum_{k=1}^\infty\left(\binom{k+1}{k-1}+6\binom{k}{k-1}\right)x^k\\ &=\sum_{k=1}^\infty\left(\binom{k+1}{2}+6\binom{k}{1}\right)x^k\\ &=\sum_{k=1}^\infty\frac{k^2+13k}{2}x^k\\ \end{align} $$ Therefore, we get the general term is $f_k=\dfrac{k^2+13k}{2}$

share|improve this answer
1  
Nice robjohn.+1 –  Adi Dani Mar 13 '13 at 17:27

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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