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