Solve the recurrence $y_{n+1} = 2y_n + n$ for $n\ge 0$ 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! 

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