# Find a formula for a sequence of number

A sequence starts at $n=1$: $\{1, 4, 13, 40, 121, 364... \}$.

Find an explicit formula that generates these numbers.

Thanks a lot!

-
Probably oeis.org/A003462 –  Andres Caicedo Oct 29 '12 at 16:46
$U_{n+1}=3U_n+1$ –  metacompactness Jun 10 '14 at 19:46
@AndresCaicedo And don't forget poor A076040. –  Balarka Sen Jun 10 '14 at 20:12

A good technique to employ on such problems is to calculate the differences between consecutive terms. Here you get:

$$\begin{array}{rcc} n:&1&2&3&4&5&6\\ a_n:&1&4&13&40&121&364\\ a_n-a_{n-1}:&&3&9&27&81&243 \end{array}$$

The numbers in the last line should look very familiar: they’re consecutive powers of $3$. It appears that $a_n=1+3+3^2+\ldots+3^{n-1}$; to get your answer, just find the sum of the geometric series.

Since you included the (recursion) label, you might also note that since the bottom line of the table seems to show that $a_n-a_{n-1}=3^{n-1}$, the sequence is apparently generated by the recurrence and initial datum

\left\{\begin{align*} &a_1=1\\ &a_n=a_{n-1}+3^{n-1}\text{ if }n>1\;. \end{align*}\right.

(The recurrence could just as well start with $a_0=0$.)

-

There are infinitely many possibilities. After all, the next term could be $-123$, or $\pi$.

But note that the given terms are $1$, $1+3$, $1+3+3^2$, $1+3+3^2+3^3$, and so on. You probably know a formula for the sum of the geometric series $1+3+3^2+\cdots +3^{n-1}$.

Remark: How did I spot this possibility? One more or less automatic thing one does with a sequence is to take differences of successive terms. We get $3$, $9$, $27$, $81$, $243$, a very familiar sequence. Actually, that's not how I knew. I remembered the numbers because they come up in a weighing puzzle. The more mathematics one has seen and done, the easier things get.

-

Let the $r$th term be $t_r$ and the sum of $r$ terms be $S_r$ where $r\ge 1$

$S_n=1+4+13+40+121+364+\cdots+t_n$

$S_n=\space\space\space\space\space\space\space\space\space 1+4+13+40+121+364+\cdots+t_n$

Subtracting $0=1+(4-1)+(13-4)+(40-13)+\cdots+(t_n-t_{n-1})-t_n$

So, $t_n=1+3+3^2+3^3+\cdots$ upto $n$ terms$=\frac{3^n-1}{3-1}=\frac{3^n-1}2$

As requested for the sum,

(1)So, $$S_n=\sum_{1\le r\le n}t_n=\frac12\sum_{1\le r\le n}\left(3^r-1\right)$$ $$=\frac12\sum_{1\le r\le n}3^r-\frac12\sum_{1\le r\le n}1=\frac12\left(\frac{3(3^n-1)}{3-1}\right)-\frac12n=\frac{3^{n+1}-2n-3}4$$

(2)

$S_n=1+4+13+40+121+364+\cdots+\frac{3^{n-1}-1}2+\frac{3^n-1}2$

$3S_n=\space\space\space\space\space\space\space 3+12+39+120+363+\cdots+\frac{3^n-3}2+\frac{3^{n+1}-3}2$

So, $$S_n-3S_n=1+(4-3)+(13-12)+\cdots+(\frac{3^n-1}2-\frac{3^n-3}2)-\frac{3^{n+1}-3}2$$

$$\implies -2S_n=-\frac{3^{n+1}-3}2+(1+1+\cdots+\text{ up to }n \text{ terms})=n-\frac{3^{n+1}-3}2=\frac{2n+3-3^{n+1}}2$$

So, $$S_n=\frac{3^{n+1}-2n-3}4$$

-
could you tell what'd be sum of such series considering n terms? . What I do is after finding tn , I write Sn two times same as you but then I multiply second Sn by 3 and then substract . Though my technique is correct but I never get the correct answer as in book , can you please confirm the answer? . Thanks –  Mr.Anubis Jan 21 '13 at 18:22
@Mr.Anubis, please find the edited answer. –  lab bhattacharjee Jan 21 '13 at 18:26
My book shows answer is n/4(3^(n+1 - 2n -3) o0 –  Mr.Anubis Jan 21 '13 at 18:31

((3^n)-1)/2