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)$.
 A: $$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.$$
A: I use generating functions since the OP here Finding the coefficient by expanding expression seems to be interested in this methodology which can be applied to non-linear recursions like this one (but is not the only one).
I show the type of calculations that can lead to solve (a) without too much thinking. Details are left to the reader.
Multilplying by $x^n$ both members of $a_{n+1}=2a_n+2^n+3$ and summing from 0 to infinity one gets the following equation for $g(x)=\sum_{n \ge 0} a_n x^n$:
$\frac{g(x)-a_0}{x}=2g(x)+\frac{1}{1-2x}+\frac{3}{1-x}$
from which:
$g(x)=\frac{a_0}{1-2x}+\frac{x}{(1-2x)^2}+\frac{3x}{(1-2x)(1-x)}$
Now from this expressions can expand again the summations ( one can perform a partial fraction decomposition for the last term) and recover $a_n$. The final result that I get is:
$a_n=a_0 2^n+2^{n-1}(n+6)-3 , n \ge 1$
For eq. (b) a similar solution pipeline can be followed.
A check of the first numbers 4, 12, 29, 65,... shows that the solution should be correct.
A: Let's try this one same way
$$a_{n+2}=a_n+4n,a(0)=1,a(1)=1$$
$$a_n=a_{n-2}+4n-4$$
It looks like a relation that jumps with $2$ everytime. So. let's assume $n$ is even and work our way through to $a_0$, and afterwards we can assume $n$ is odd and work our way through to $a_1$
$$2|n \implies n=2k, \  k \in \{0,1,2,\dots\}$$
$$a_{2(k+1)}=a_{2k}+8k\implies a_{2k}=a_{2(k-1)}+8(k-1)$$
$$\implies a_{2(k+1)}=a_{2(k-1)}+8k+8(k-1)=a_{2(k-1)}+8(k+k-1)$$
$$=a_{2(k-2)}+8(k+(k-1)+(k-2))$$
So, by induction,
$$a_{2(k+1)}=a_2+8(k+(k-1)+\dots+1)$$
and of course, from the original formula, $a_2=a_0=1$, giving
$$a_{2(k+1)}=\frac{8k(k+1)}{2}+1$$
$$ \implies a_{2m}=\frac{8m(m-1)}{2}+1=(2m-1)^2 \ \forall m \in \mathbb{N_0} $$
Now, assume $n=2k-1$ and $k \in \mathbb{Z^{+}}$, substituting that in the original formula, we get
$$a_{2(k+1)-1}=a_{2k-1}+4(2k-1) \implies a_{2k-1}=a_{2(k-1)-1}+4(2(k-1)-1)$$
$$\implies a_{2(k+1)-1}=a_{2(k-1)-1}+4((2k-1)+(2(k-1)-1))$$
and so on, by induction,
$$a_{2(k+1)-1}=a_1+4\left(\sum_{i=1}^{k}(2i-1)\right)=1+4k^2$$
$$\implies a_{2m-1}=1+4(m-1)^2=4m^2-8m+5$$
for all $m \in \mathbb{Z^{+}}$ and $a_{2m}=(2m-1)^2$ for all $m \in \mathbb{N_0}$. Now,
$$n=2m \implies a_{n}=(n-1)^2$$
$$n=2m-1 \implies m = \frac{n+1}{2}$$
$$ \implies a_{n}=4\left(\frac{n+1}{2}\right)^2-8\left(\frac{n+1}{2}\right)+5$$
$$ \implies a_{n}=(n-1)^2+1$$
So, to eliminate having two formulas, we can say
$$a_{n}=(n-1)^2 + \frac{1}{2}(1-(-1)^n)$$
That way, if $n$ is odd, the part with the half will be $1$; if even, it'll be zero.
So, there you have it, the formula for $a_n$ for both even and odd $n \ \ \Box.$
