# Inhomogeneus recurrence relation $a_{n+1} = 2a_n+3^n+4^n$

So this was given in class and the teacher weren't able to solve it, and I was wondering how a solution can be given?

$a_{n+1} = 2a_n+3^n+4^n, \enspace a_0 = 1$

Usually we'd consider the solution $a_n$ to be of the form $a_n = a_n^{(h)}+a_n^{(p)}$, where $a_n^{(h)}$ is a solution to the homogeneous recurrence relation and $a_n^{(p)}$ is a particular solution to the recurrence relation. Thus $a_n^{(h)} = c_1\times 2^n$ and $a_n^{(p)} = c_2(3^n+4^n)$, but this strategy didn't work, as solving for $c_2$ in $c_2(3^{n+1}+4^{n+1})+c_2(3^n+4^n) = 3^n+4^n$ there doesn't seem to be a way to cancel out the $n$'s this equation. Is there maybe another strategy that would make this possible to solve?

• fro 4 n \to \infty $your difference equation becomes$ y'(x)=y(x)+3^{x}+4^{x} $solve this and you will have an approximate solution – Jose Garcia Nov 14 '14 at 12:48 ## 3 Answers $$\dfrac{a_{n+1}}{2^{n+1}} = \dfrac{a_n}{2^n} + \dfrac{1}{2}(\dfrac{3}{2})^n + \dfrac{1}{2}2^n$$ Let$b_{n+1} = \dfrac{a_{n+1}}{2^{n+1}}$, we have $$b_{n+1} = b_n + \dfrac{1}{2}(\dfrac{3}{2})^n + \dfrac{1}{2}2^n$$ so$b_n = b_0 + \sum_{k=1}^n\left(\dfrac{1}{2}(\dfrac{3}{2})^k + \dfrac{1}{2}2^k\right)$Can you go from this?(In general for$a\neq 1$, we have$\sum_{k=1}^n a^k = \dfrac{a-a^{n+1}}{1-a}$) • I'm not sure how to simplify$\sum_{k=1}^n \left(\left(\frac{3}{2}\right)^k+2^k\right)$. Can it be done? – Frank Vel Nov 14 '14 at 13:00 • @fvel just a sum of geometric series: if$q\ne 1$, then$\sum_{k=0}^n = \frac{q^{n+1}-1}{q-1}$. – TZakrevskiy Nov 14 '14 at 13:04 • @fvel I've added one line at the end – Petite Etincelle Nov 14 '14 at 13:07 • I realised I can do$\sum_{k=1}^n\left(\left(\frac{3}{2}\right)^k +2^k\right) = \sum_{k=1}^n\left(\frac{3}{2}\right)^k + \sum_{k=1}^n2^k$and I'm stupid :( – Frank Vel Nov 14 '14 at 13:10 • Nice manipulation :) – Chinny84 Nov 14 '14 at 13:10 Let$G(x)$be the generating function of the sequence;$ G(x) = \sum\limits_{i=0} a_ix^i $Then from your recurrence we have$ \frac{G(x)-1}{x} = 2G(x) + \sum\limits_{i=0} 3^ix^i + 4^ix^i = 2G(x) + \frac{1}{1-3x} + \frac{1}{1-4x}$Solving for$G(x)$, $$G(x) = \frac{1}{1-2x} + \frac{x}{1-2x} \left( \frac{1}{1-3x} + \frac{1}{1-4x}\right).$$ Finally, we expand$G(x)$in powers of$x$to find$ a_n = \frac{1}{2}(-2^n + 2*3^n + 4^n) \$.
$$a_n = 2^n+\sum_{k=0}^{n-1}\left((3^k+4^k)2^{n-1-k}\right).$$
$$a_n=2^n+2^{n-1}\frac{(3/2)^n-1}{3/2-1} + 2^{n-1}\frac{2^n-1}{2-1} = 3^n + 4^n/2-2^{n-1}, \quad n\ge 1.$$