I am given the following recurrence relation: $a_{n+1} = 3a_n+1$ where $a_0 = 1$ which gives these values for the first 5 numbers: $1, 4, 13, 40, 121$, where I must find a specific formula $a_n$ how would I go about calculating the conjecture for this?
It's clear to me it follows the standard of an arithmetic series, though what are the steps to figuring it out?
Here is my rational so far (after some digging):
$a_1 = 1$
$a_2 = 3a_1+1 = 4$
$a_3 = 3a_2+1 = 13$
$a_4 = 3a_3+1 = 40$
$a_5 = 3a_4+1 = 121$
Then taking the differences of the result:
difference between $1 \& 4 = 3; 4\&13 = 9; 13\&40 = 27; 40\&121 = 81$
Then taking the differences of the differences:
difference between $3\&9 = 6; 9\&27 = 18; 27\&81 = 54$
again …
$6\&18 = 12; 18\&54 = 36$
$12\&36 = 24$
Get the last number in its lowest term which is $24/12 = 2$
Hence the series must be divisible by 2.
Given that each difference is $3^n$
We then get:
$\frac{3^na_n-1}{2}$ because of $a_0 = 1$ we must minus by 1 to get the term $a_0=1$
Best Answer
We are given the recurrence system $$a_{n+1}=3a_n+1,\\a_0=1.$$ Preliminary observations: Its difference equation is a first-order linear recurrence relation, which generates a sequence in which the consecutive differences between consecutive terms have a common ratio, i.e., the difference between consecutive terms is successively multiplied by a common ratio. (In our example the common ratio is $3$.) Arithmetic and geometric sequences are actually special cases of such a sequence.
We can derive its closed form (general term) using the formula for geometric series:
$$a_0=1\\ a_1=3+1\\ a_2=3^2+3+1\\ a_3=3^3+3^2+3+1\\ a_4=3^4+3^3+3^2+3+1\\ \cdots\\ a_n=3^n+\frac{1(3^n-1)}{3-1}\\ =\frac123^{n+1}-\frac12\quad(n\geq0).$$
In general, when $r\neq1,$ the recurrence relation $a_{n+1}=ra_n+d$ has closed form $$a_n=a_0r^n+\frac{d(r^n-1)}{r-1}\quad(n\geq0).$$ Since this is of the form $$a_n=\alpha r^n+\beta,\tag{*}$$ once a sequence has been identified as such, we can simply plug $n=0,1$ into $(\text*)$ to form a pair of simultaneous linear equations then solve for $\alpha$ and $\beta.$