Solving $A_{n+1}=3A_n+2^n$

Question

Let's say I want to find a formula for the following expression given $n$ number of threes $$\ldots(3(3(3(3(3(3+1)+2)+4)+8)+16)+\ldots$$ If $A_0=1$, then $$A_{n+1}=3A_n+2^n$$ Plugging in values to see the pattern, $$A_2 = 3+1$$ $$A_3 = 3^2+3+2^1$$ $$A_4 = 3^3+3^2+3\cdot2+2^2$$ But I don't know how to condense something like this into an explicit formula.

Answer 1

One way to see the correct answer is to use that:

$$x^n-y^n=(x-y)\left(x^{n-1}+x^{n-2}y+\cdots+xy^{n-2}+y^{n-1}\right)$$

Putting in $x=3,y=2$ you get that:

$$3^n-2^n = 3^{n-1}+3^{n-2}\cdot2+\cdots+3\cdot 2^{n-2}+2^{n-1}$$

Now add $3^n$ to both sides, and you get:

$$2\cdot 3^n -2^n = 3^{n}+3^{n-1}+3^{n-2}\cdot2+\cdots+3\cdot 2^{n-2}+2^{n-1}$$

There are more advanced techniques to solve this sort of equation generally, but this is a good "eyeball" solution without appeal to generating functions.

---

The generating function approach is to write:

$$f(z)=\sum_{n=0}^{\infty} A_nz^n = A_0 + z\sum_{n=1}^{\infty} (3A_{n-1}+2^{n-1})z^{n-1} = 1+z\left(3f(z)+\frac{1}{1-2z}\right)$$ Solving for $f(z)$ gives us $$f(z)=\frac{1}{1-3z}\left(1+\frac{z}{1-2z}\right)=\frac{1-z}{(1-2z)(1-3z)}$$

You can then use partial fractions to get that:

$$f(z)=\frac{2}{1-3z}-\frac{1}{1-2z}$$

Thus giving $A_n=2\cdot 3^n-2^n.$

Answer 2

In this answer I will provide a solution to the problem:

Given $A_0=1$ and $A_{n+1}=3A_n+2^{n-1}$ for all non-negative $n$, find the expression for $A_n$.

The answer should be $2\times 3^n-2^n$, and here is how you can obtain it without induction. As mentioned in ultrainstinct's answer, this is a inhomogeneous recursive relation and the following is how it can be made homogeneous (with the cost of increasing the order from 1 to 2).

$$A_{n+2}=3A_{n+1}+2^n,$$ $$2A_{n+1}=6A_n+2^n,$$

Substract them to get a homogeneous recurring relation, $$A_{n+2}=5A_{n+1}-6A_n,$$

The characteristic equation for this is just $x^2-5x+6=0$, and the two roots are $x=2$ and $x=3$. Now you have the general solution,

$$A_n=C_1\times 3^n+C_2\times 2^n,$$

You can determine the constants $C_1$ and $C_2$ from the initial conditions.

Answer 3

This is a non homogeneous linear recurrence relation. Usually with non-homogeneous equations of this form we split the solution up into a homogeneous one and a particular one. In this case we solve the homogeneous case first, so label it $h_n$. $$h_{n+1} = 3 h_n$$ assume $h_n = r^n$, plug it in and we get $r^{n+1} = 3r^n$, we can divide out by $r^n$ since a $0$ solution is trivial. Generally if you find a bunch of roots, you take a linear combination of them. So in our case, the homogeneous solution is

$$h_n = c_13^n$$ now onto the particular solution, let's name it $p_n$, in this case we "pick" a solution of the form $$p_n = a2^n + b$$ now plug it in

$$a2^{n+1}+b = 3a2^{n} + 3b + 2^n$$ Simplified we get $$-a2^n -2b = 2^n$$ matching coefficients we get $a=-1$ and $b=0$ so now our solution is

$$A_{n}=p_n+h_n = c_13^n-2^n$$ now use your initial condition of $A_0=1$ to get $$A_0=1=c_1-1\implies c_1=2$$ So your final solution should be

$$A_n = 2\cdot 3^n - 2^n$$

This doesn't tell you why we chose the forms of the solutions that we did. But this is the general process of solving equations like these.

Answer 4

Solution of the recurrence Given sequences $g(n) \neq 0$ and $b(n)$, we have that $f(n)$ the solution of the recurrence $$f(n+1)=g(n).f(n)+b(n)$$ is given by $$f(n)= \bigg(\sum^{n-1}_{p=1}\frac{b(p)}{\prod\limits^{p}_{k=1}g(k)}+f(1) \bigg)\prod^{n-1}_{k=1}g(k). $$ See the proof here

Now taking $g(n)= 3$ and $b(n) =2^n.$ One obtains $$A_n= \prod^{n-1}_{k=1}3\bigg(\sum^{n-1}_{p=1}\frac{2^p}{\prod\limits^{p}_{k=1}3}+A_1 \bigg)= 3^{n-1}\bigg(\sum^{n-1}_{p=1}\frac{2^p}{3^p}+A_1 \bigg)\\=3^{n-1}\bigg(\frac{2}{3}\frac{\left(\frac{2}{3}\right)^{n-1}-1}{\frac{2}{3}-1}+A_1 \bigg)=3^{n-1}\bigg(2\left[1-\left(\frac{2}{3}\right)^{n-1}\right]+A_1 \bigg)\\=\left(2\cdot 3^{n-1}-2^n+ 3^{n-1}\cdot A_1\right).$$

Finally, With $A_1= 4$ since $A_0=1$ $$A_n=\left(2\cdot 3^{n-1}-2^n+ 3^{n-1}\cdot 4\right) = 2\cdot 3^{n}-2^n$$

Answer 5

We can find the general formula with algebra of some operators.

Define $E^k$ on operator that makes $E^k a_n= a_{n+k}$, then we can write that recurrence in the form

$$ (E-3)a_n=2^n\;\;\;\;\;\;(1) $$ We can show that the operator $E-s$ cancel terms in the form $c.s^n$, $$(E-s)s^n =s^{n+1}-Es^{n}=s^{n+1}-s^{n+1}=0. $$

So apply $E-2$ in $(1)$.

We have $$(E-2)(E-3)a_n=0. $$

It can be shown, that we can reverse, and find the solution in the form of sums of the terms

$$a_n=c_12^n+c_23^n \;\;\;\;(2).$$

But now is easy with the initial conditions to find $c_1$ and $c_2$.

From $(1)$, and applying $(E-3)$ in $(2)$ we have

$$(E-3)a_n=c_1(E-3)2^n=c_1(2^{n+1}-32^n)=c_12^n(2-3)=-c_12^n=2^n .$$ So $c_1=-1$.

Apply $n=0$ in $(2)$, $$a_0=c_2-1=1, $$ so $c_2=2.$

Then $$a_n=2.3^n-2^n. $$