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?

Thanks in advance.

  • $\begingroup$ 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 $\endgroup$ – Jose Garcia Nov 14 '14 at 12:48

$$\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}$)

  • $\begingroup$ 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? $\endgroup$ – Frank Vel Nov 14 '14 at 13:00
  • 1
    $\begingroup$ @fvel just a sum of geometric series: if $q\ne 1$, then $\sum_{k=0}^n = \frac{q^{n+1}-1}{q-1}$. $\endgroup$ – TZakrevskiy Nov 14 '14 at 13:04
  • $\begingroup$ @fvel I've added one line at the end $\endgroup$ – Petite Etincelle Nov 14 '14 at 13:07
  • $\begingroup$ 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 :( $\endgroup$ – Frank Vel Nov 14 '14 at 13:10
  • $\begingroup$ Nice manipulation :) $\endgroup$ – 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) $.


Just write down the first couple of terms and make a hypothesis that the solutions have the form

$$a_n = 2^n+\sum_{k=0}^{n-1}\left((3^k+4^k)2^{n-1-k}\right).$$

The proof of this formula should be quite easy by induction. Even further, one can simplify it into

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.