Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

So I have been assigned this problem for my discrete math class and am getting nowhere. The book for the class doesn't really have anything on recurrences and the examples given in class are not helpful at all. I seem to be going in circles with the math. Any help with this problem would be GREATLY appreciated.

Solve the recurrence $$y_{n+1} = 2y_n + n$$ for non-negative integer $n$ and initial condition $y_0 = 1\;$ for

a) Ordinary generating series
b) Exponential generating series
c) Telescoping
d) Lucky guess + mathematical induction
e) Any other method of your choice

Thanks in advance!

share|cite|improve this question

Using ordinary generating functions


gets transformed into

$$\sum_{n=0}^\infty y_{n+1}x^n=2\sum_{n=0}^\infty y_nx^n+\sum_{n=0}^\infty nx^n$$

$$\sum_{n=0}^\infty y_{n+1}x^n=2 y(x)+x\sum_{n=1}^\infty nx^{n-1}$$

$$\sum_{n=0}^\infty y_{n+1}x^n=2 y(x)+x\frac{1}{(1-x)^2}$$

$$\sum_{n=0}^\infty y_{n+1}x^{n+1}=2x y(x)+x^2\frac{1}{(1-x)^2}$$

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

$$\sum_{n=0}^\infty y_{n}x^{n}=2x y(x)+x^2\frac{1}{(1-x)^2}+y_0$$

$$y(x)=2x y(x)+x^2\frac{1}{(1-x)^2}+y_0$$

$$(1-2x) y(x)=x^2\frac{1}{(1-x)^2}+y_0$$

$$ y(x)=x^2\frac{1}{(1-2x)(1-x)^2}+\frac{y_0}{1-2x}$$

Can you match the coefficients now?

share|cite|improve this answer

For d) I find $$\begin {array} {r r} n&y_n\\0&1\\1&2\\2&5\\3&12\\4&27\\5&58\\6&121\\7&248 \end {array}$$ from a spreadsheet. This gives the conjecture $y_n=2^{n+1}-(n+1)$. $y_0=2^1-1=1$ works. Assume $y_n=2^{n+1}-(n+1)$, then $y_{n+1}=2y_n+n=2(2^{n+1}-(n+1))+n=2^{n+1+1}-(n+1+1)$

share|cite|improve this answer

It is possible to avoid generating functions altogether. Let $y_n=a_n+b_n$ such that $a_{n+1}=2a_n$ Let $b_n= sn+c$

Then $sn+s +c=2sn+2c+n$

Solving, $s=c=-1$ Also, $b_0=-1,a_0=2$

So $y_n=2^{n+1}-n-1$

share|cite|improve this answer

Your Answer


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.