I have the following solution for solving a recurrence using a generating function and I have a question on why it is multiplied by (1-z) and why this causes the second summand to disappear. 
Asked
Active
Viewed 441 times
2
user2057890
- 157
-
1$z$ seems to be back in the line after the next line. So, just a typo I guess. – voldemort Jan 22 '15 at 14:50
-
The limit on the sum changed, as did the the exponent on the z inside. Note that the exponent on the 2 has been mistakenly written as a subscript instead of a superscript. – Joffan Jan 22 '15 at 15:13
-
Yes, I thought so. What is happening in the next line after the next line, why is A(z) multiplied by (1-z) and why does that cause the second summand to disappear? – user2057890 Jan 22 '15 at 15:16
1 Answers
2
After correcting the typos, we have
$$\begin{align*} A(z)&=2+z\sum_{n\ge 1}a_{n-1}z^{n-1}+z\sum_{n\ge 1}2^{n-1}z^{n-1}\\ &=2+z\sum_{n\ge 0}a_nz^n+z\sum_{n\ge 0}2^nz^n\\ &=2+zA(z)+z\sum_{n\ge 0}2^nz^n\;, \end{align*}$$
since $A(z)=\sum_{n\ge 0}a_nz^n$. Now just subtract $zA(z)$ from both sides to get
$$(1-z)A(z)=A(z)-zA(z)=2+z\sum_{n\ge 0}2^nz^n\;.$$
Brian M. Scott
- 616,228
-
-
@user2057890: Sum of a geometric series with first term $1$ and ratio $2z$: $2^nz^n=(2z)^n$. – Brian M. Scott Feb 01 '15 at 15:25