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.

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|improve this question
add comment

3 Answers

Using ordinary generating functions

$$y_{n+1}=2y_n+n$$

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|improve this answer
add comment

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|improve this answer
add comment

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|improve this answer
add comment

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.