Finding general formula for a recursion function

Question

If we have a recursion relation defined as $a_n = 3a_{n-1}+1$ with $a_1=1$ then find the general formula for $a_n$ in terms of $n$ with a(1) = 1.

So far I have:

$a_n = 3a_{n-2}+1+1 = 3a_{n-3}+1+1+1 = 3a_{n-4}+1+1+1+1$

I'm unsure of where to go from here to find the solution.

Answer 1

Note that $$a_{n}+\frac 12=3\left(a_{n-1}+\frac 12\right).$$ So, letting $b_n=a_n+1/2$, we get $$b_n=3b_{n-1}.$$ Since $b_1=a_1+1/2=3/2$, we have $$b_n=\frac 32\cdot 3^{n-1}=\frac{3^n}{2}.$$ Hence, we have $$a_n=\frac{3^n}{2}-\frac 12=\frac{3^n-1}{2}.$$

Answer 2

Let's prove by induction that:

$$a_n = \frac{3^n-1}{2}$$

For $n = 1$, we have $\frac{3^1-1}{2} = 1 = a_1$. So that's good so far.

Assume our formula holds for $1\leq k \leq n$. Then:

$$a_{n+1} = 3a_n + 1 = 3\frac{3^n-1}{2} + 1 = \frac{3^{n+1}-3+2}{2} = \frac{3^{n+1}-1}{2}$$

Wich is what we wanted to prove.

($a_n = 1 + 3 + 9 + \ldots + 3^{n-1}$. This is called geometric series. You can find quite a lot of info about it).

Answer 3

Inductions and guessing are good, but it's better to handle problems like this in a more fundamental way, i.e. using generating function. It's harder but in the long run it is an invaluable tool for recurrences and much more. So you got $$ a_{n+1} = 3 a_n +1 $$ Define $G(z) = \sum_{k=0}^{\infty} a_k z^k$. Now multiply both sides of the equation by $z^k$ and sum over $k$. On the RHS you get $3 G(z) + \frac{1}{1-z}$. On LHS after a bit of algebra you get $\frac{G(z) - a_0}{z}$. Now after some rearrangement you get $$ G(z) = \frac{a_0}{1-3z} + \frac{z}{(1-3z)(1-z)} = \frac{\frac{1}{2}-a_0}{1-3z} - \frac{1}{2(1-z)} =(\frac{1}{2}- a_0) \sum_{k=0}^{\infty} 3^k z^k - \frac{1}{2}\sum_{k=0}^{\infty} z^k $$ Now all you need to do is combine coefficients to get the value of the $\text{n}^{\text{th}}$ term: $$ a_n = \frac{(1-2 a_0)3^{n}-1}{2} $$ If $a_0=0$, you get $$ a_n = \frac{3^n -1}{2} $$

Answer 4

There is a direct method for solving problems of this kind. I'll give the general case and then apply it to this specific example.

Let our sequence be of the form $a_n = \alpha a_{n-1} + \beta$ for $\alpha, \beta\in\mathbb{R}$, then by repeated substitution we obtain \begin{align*} a_n &= \alpha a_{n-1} + \beta \\ &= \alpha^2a_{n-2} + \alpha\beta + \beta\\ &= \alpha^3a_{n-3} + \alpha^2\beta + \alpha\beta + \beta\\ &\;\,\vdots \\ &= \alpha^{n-1}a_1 + \sum_{i=0}^{n-2}\beta\alpha^i \end{align*} so when $\alpha = 1$ then $a_n = a_1 + (n-1)\beta$ and when $\alpha\ne 1$ then we apply the formula for the geometric partial sum and obtain

$$ a_n = \alpha^{n-1}a_1 +\beta\frac{\alpha^{n-1} - 1}{\alpha - 1} $$

In our case $\alpha = 3, \beta = 1$ and $a_1 = 1$, so substituting these in and simplifying gives

$$ a_n = \frac{3^n - 1}{2} $$

The good thing about doing it this way is that you can instantly see not only which sequences converge, but also what their limit is. The sequence $a_n=\alpha a_{n-1} + \beta$ converges if and only if $|\alpha|<1$ and the limit is

$$\lim_{n\to\infty}a_n = \sum_{i=0}^\infty\beta\alpha^i = \frac{\beta}{1-\alpha}$$

This is because when $|\alpha|<1$ then $\alpha^{n-1}$ goes to $0$, killing the $\alpha^{n-1}a_1$ term, and it is the radius of convergence for the geometric series. So in particular your sequence diverges. I know convergence wasn't part of the question but it's useful to know!