Solving recurrence relation with initial conditions given

Question

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

Answer 1

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

Answer 2

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.

Answer 3

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