Solve the recurrence relation $u_n = 2u_{n-1} + 2^n - 1$ where n is greater than or equal to 1 and $u_0=0$.
We have characteristic root equal to 2 with multiplicity 1. So homogeneous part will have solution $A.2^n$, where A is constant. The particular solution should be of the form $P.n.2^n + Q$, where P, Q are constants. Now when I put this in original recurrence I can't solve. Plz help.
HINT: Multiply out the righthand side:
$$\begin{align*} Pn2^n+Q&=2P(n-1)2^{n-1}+2Q+2^n-1\\ &=P(n-1)2^n+2Q+2^n-1\\ &=Pn2^n-(P-1)2^n+2Q-1 \end{align*}$$
Subtract $Pn2^n+Q$ from both sides and rearrange a little:
$$Q-1=(P-1)2^n$$
This has to hold for all $n\ge 0$, so what must $P$ be? And what does that force $Q$ to be?