2

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!

amWhy
  • 209,954
Northpaw
  • 33

3 Answers3

3

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?

Pedro
  • 122,002
2

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

Ross Millikan
  • 374,822
1

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$

Ishan Banerjee
  • 6,459