# Still stuck on recurrence

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.

-
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
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

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)$.

-

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.

-

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$.

-