<s>[INST] Solving recurrence relation with initial conditions given I am trying to solve 2 recurrence equations:
a) $a_{n+1} = 2a_n + 2^n + 3, a(0)=4$
b) $a_{n+2} = a_n + 4n, a(0)=1, a(1)=1$
For (a), I don't know how to deal with $2^n$ part.
For (b), I am confused because $a(0)=a(1)$.
 [/INST] $$a_{n+1}=2a_n+2^n+3,a(0)=4$$
Let's try it a bit:
$$a_{n+1}=2(2a_{n-1}+2^{n-1}+3)+2^n+3=4a_{n-1}+2\cdot2^{n}+(3+3\cdot2)$$
$$a_{n-1}=2a_{n-2}+2^{n-2}+3 \implies a_{n+1}=4(2a_{n-2}+2^{n-2}+3)+2\cdot2^{n}+9$$
$$\iff a_{n+1}=8a_{n-2}+3\cdot2^n+(3+3\cdot2+3\cdot4)$$
So, we can conjecture, (and we shall prove by induction): let $k$ be a positive integer,
$$a_{n+1}=2^{k+1}\cdot a_{n-k}+(k+1)\cdot2^{n}+3(1+2+\dots+2^k)$$
Now, with our base case $k=0$, we can have the inductive assumption:
$$P_m:a_{n+1}=2^{m+1}\cdot a_{n-m}+(m+1)\cdot2^{n}+3(1+2+\dots+2^m)$$
So, we shall prove
$$P_{m+1}:a_{n+1}=2^{m+2}\cdot a_{n-m-1}+(m+2)\cdot2^{n}+3(1+2+\dots+2^{m+1})$$
Now, by our original equation, 
$$a_{n-m}=2a_{n-m-1}+2^{n-m-1}+3$$
So,
$$a_{n+1}=2^{m+1}\cdot (2a_{n-m-1}+2^{n-m-1}+3)+(m+1)\cdot2^{n}+3(1+2+\dots+2^m)$$
$$a_{n+1}=2^{m+2}a_{n-m-1}+2^{n}+3\cdot 2^{m+1}+(m+1)\cdot2^{n}+3(1+2+\dots+2^m)$$
$$=2^{m+2}a_{n-m-1}+(m+2)\cdot2^{n}+3(1+2+\dots+2^m+2^{m+1}) \ \Box.$$
So, now we've proved:
$$a_{n+1}=2^{k+1}\cdot a_{n-k}+(k+1)\cdot2^{n}+3(1+2+\dots+2^k)$$
$$=2^{k+1}\cdot (a_{n-k}+3)+(k+1)\cdot2^{n}-3 \tag{by geometric series formula}$$
Putting $k=n$ to relate it to $a_0$, we get
$$a_{n+1}=2^{n+1}\cdot (a_0+3) + (n+1) \cdot 2^{n}-3 =7 \cdot 2^{n+1}+ (n+1) \cdot 2^{n}-3 $$
$$\implies a_n = 7 \cdot 2^{n}+ n2^{n-1}-3 =2^{n-1}(n+14)-3 \ \Box.$$
</s>