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.

I am still stuck on this problem and it is very frustrating. I need to solve this using exponential generating series and again with telescoping. Problem is I am not even sure what telescoping is and my googling has not been very helpful. Thanks in advance.

Solve the recurrence $y_{n+1} = 2y_n + n$ for non-negative integer n and initial condition $y_0=1$ for Using
1. Exponential generating series
2. Telescoping.

share|improve this question
    
Use \$ \$ to denote your code, so that the LaTeX displays properly. –  Calvin Lin Feb 2 '13 at 18:01
    
Thanks. I did not know that! –  Northpaw Feb 2 '13 at 18:19
1  
It would be better to make a comment on your other question math.stackexchange.com/questions/290616/… –  Ross Millikan Feb 2 '13 at 18:23
    
This is true. Im new here and was unsure what the usual protocol is. :/ –  Northpaw Feb 2 '13 at 21:43

3 Answers 3

Telescoping - Observe that $y_{n+1} + (n+2) = 2( y_n + (n+1) )$.

So, if we set $x_n = y_n + (n+1)$, ($x_0 = 2$), we easily see that $x_n = 2^{n+1}$ by telescoping series.

Thus, $y_n = 2^{n+1} - (n+1)$.

share|improve this answer

The trick is to work backwards $$y_{n+1}=n+2y_n$$ $$=n+2(2y_{n-1}+(n-1))$$ $$=n+2(n-1)+2^2(2y_{n-2}+(n-2))$$ $$=n+2(n-1)+2^2(n-2)+2^3(n-3)+...+2^n(n-n)$$ So we have $$ y_{n+1}=\sum_{i=0}^n2^i(n-i)=n\sum_{i=0}^n2^i+\sum_{i=0}^ni2^i$$ I suspect you can take it from here.

Well, I guess this doesn't really use generating functions, so this is probably not what you want.

share|improve this answer

For exponential generating functions, define: $$ \widehat{Y}(z) = \sum_{n \ge 0} y_n \frac{z^n}{n!} $$ Take your recurrence, multiply by $\frac{z^n}{n!}$, sum over $n \ge 0$, and see how to express the result in terms of $\widehat{Y}$ and its derivatives. The initial condition to the recurrence translates into $\widehat{Y}(0) = 1$.

Also try the ordinary generating function $Y(z) = \sum_{n \ge 0} y_n z^n$: multiply by $z^n$ and sum, express the result in terms of $Y(z)$ and $z$.

share|improve this answer

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.