Mdthbs

How do you work out the nth term of a sequence that's neither arithmetic or geometric where two operations are used to get from one term to the next? For example, the sequence 3, 10, 31, 94, 283 where each term is the last term multiply 3 plus 1. (i.e $u_1 = 3$ and $u_{n+1} = 3u_n + 1$). Then is there a way to generalise it where $u_1 = a$ and $u_{n+1} = bu_n + c$?

This problem was part of a question on the Oxford MAT. I've tried to find common differences, substitute terms and many other methods. Also I found that this problem fits in an area of maths called recurrence relations but the Wikipedia page was far too confusing for me since I'm only year 11 (grade 10), so it didn't help answer my question. I wonder if there's a simpler explanation for this problem. Thanks in advance

There's a nice trick for recursive sequences of this type, where $u_{n+1}$ is a linear function of $u_n$: find a constant $r$ such that $u_{n+1}-r$ is a constant multiple of $u_n-r$. In this case, the multiplication factor in the linear function is $3$, so we're searching for an $r$ with $u_{n+1}-r = 3(u_n-r)$. Solving for $r$:
begin{align*}
u_{n+1}-r &= 3(u_n-r) \
(3u_n+1)-r &= 3u_n-3r \
1+2r &= 0 \
r &= -tfrac12.
end{align*}

Why does this help us? Because $u_{n+1}+frac12 = 3(u_n+frac12)$, it's easy to prove by induction that $u_n+frac12 = 3^{n-1}(u_1+frac12)$ for all $nge1$. (In other words, this slightly shifted version of the sequence really is geometric.) Solving for $u_n$:
begin{align*}
u_n+tfrac12 &= 3^{n-1}(u_1+tfrac12) \
u_n &= 3^{n-1}(3+tfrac12)-tfrac12 \
u_n &= tfrac12(7cdot3^{n-1}-1).
end{align*}
(Of course there's some formula we could memorize that gives the answer immediately, which is fine ... but it's always best to know how such formulas are derived in the first place.)

Observe that
begin{align*}
u_{n+1}&=3u_n+1\
u_n&=3u_{n-1}+1
end{align*}

Then

$$(u_{n+1}-u_n)=3(u_n-u_{n-1}).$$

Let us define $a_n=u_n-u_{n-1}$, then the above equation can be written as
$$a_{n+1}=3a_n.$$
This gives us

begin{align*}
a_3&=3a_2\
vdots & =vdots\
a_{n+1}&=3a_n
end{align*}
If we multiply these out, we get

$$a_{n+1}=3^{n-1}a_2$$

So we have
$$u_{n+1}-u_n=3^{n-1}(u_2-u_1)=3^{n-1} ,7.$$

Now add these:

begin{align*}
u_2-u_1 &=3^{0} ,7\
u_3-u_2 &=3^{1} ,7\
u_4-u_3 &=3^{2} ,7\
vdots & =vdots\
u_{n+1}-u_n &=3^{n-1} ,7
end{align*}
To get
$$u_{n+1}-u_1=7(3^0+3^1+dotsb +3^{n-1})$$
Thus,

$$u_{n+1}=7left(frac{3^n-1}{2}right)+3 =frac{1}{2}left(7. , 3^{n}-1right)quad text{ for } n geq
color{red}{0}.$$
In fact, you can test that validity of this expression by plugging $n=0$ to get $u_1=3$, with $n=1$ we get $u_2=10$ and so on.

Try writing down the first few terms then observe how the coefficients are truncated. if the first term is $u_1$,

I found that the $n^{th}$ term is:

$$u_n = b^{n-1}u_1 + c*sum_{i=2}^n a^{n-i}$$

Set $v_n=u_n+a$ to try to get the recurrence to be $v_{n+1}=3v_n$. So, you want
$$u_{n+1}+a=3u_n+3a$$
that is
$$3u_n+1+a=3u_n+3a.$$
Therefore you want $a=1/2$. So the sequence $v_n$ is $7/2$, $21/2$, $63/2$ etc. Then
$$v_n=3^{n-1}frac72$$
and
$$u_n=3^{n-1}frac72-frac12.$$

I have worked out this sum for your sequence: $$u_{n}=left (sum_{i=0}^{n}3^{i} right ) - 3^{n-1}$$. You can easily find it if you substitute recursively values in the formula. For example for $n=4$ it's $3^{4}+3^{2}+3^{1}+1$. I obtain a geometric progression (but there isn't $3^{3}$) and the sum in general is: $$u_{n}=frac{1-3^{n+1}}{1-3}-3^{n-1}$$.
In the end: $$u_{n}=frac{1}{2}(3^{n+1}-1)-3^{n-1}$$

For the second question: $$u_{n}=ab^{n-1}+sum_{i=0}^{n-1}cb^{i}=ab^{n-1}+frac{(cb)^{n-1}-1}{cb-1}$$