Recurrence Relation First Five Terms

Question

Currently in my discrete math class we are working on Recurrence Relations and sequences. Now there are similar problems to mine on here but I could not find what I was looking for. My teacher for this class just plain cannot teach and was hoping someone could help explain this to me.

The problem I have is to find the first five terms of this sequence: $a_n=3a_{n-1} - 1$; with $a_1 = 1$

Then I have to find an explicit or closed definition for this sequence? If anyone could please offer up some help it would truly be appreciated.

Answer 1

$$a_2=3a_1=(3^1)a_1-(3^0)$$ $$a_3=3(3a_1-1)-1=9a_1-4=(3^2)a_1-(3^0+3^1)$$ $$a_4=3(9a_1-4)-1=27a_1-13=(3^3)a_1-(3^0+3^1+3^2)$$ and so forth. Since $a_1=1$, we get

$$a_n=3^{n-1}-\sum_{k=0}^{n-2}{3^k}$$

Inductive proof as requested: $$a_1=1$$ $$a_n=3a_{n-1}-1 (A)$$ Show that $$a_n=3^{n-1}-\sum_{k=0}^{n-2}{3^k} (B)$$ Step $1$: Prove for $n=2$. $$A\rightarrow a_2=3\cdot1-1=2$$ $$B\rightarrow a_2=3^1-\sum_{x=0}^{0}{3^x}=3^1-3^0=2$$ Hence proved true for $n=2$.

Inductive step: Assume true for $n=k$, then show for $n=k+1$

Via statement $A$ we are showing that $a_{k+1}=3a_k-1$ $$a_k=3^{k-1}-(3^0+...+3^{k-2})$$ $$a_{k+1}=3^{k}-(3^0+...+3^{k-1})$$ $$\frac{1}{3}a_{k+1}=3^{k-1}-(3^{-1}+...+3^{k-2})$$ $$\frac{1}{3}a_{k+1}=3^{k-1}-(3^0+...+3^{k-2})-\frac{1}{3}$$ $$\frac{1}{3}a_{k+1}=a_k-\frac{1}{3}$$ $$a_{k+1}=3a_k-1$$ Hence we have proved the statement true for $n=2$, and for $n=k+1$ when $n=k$ has been assumed, hence the statement is true for all $n \in \Bbb Z, n\ge 2$.

Answer 2

Constructing the first terms of the sequence as suggested in the comments you can also arrive at a closed expression. As example, from:

$$ a_4=3a_3-1=3(3a_2-1)-1=3(3(3a_1-1)-1)-1=3(3(3\cdot 1-1)-1)-1=3(3^2-3-1)-1=3^3-3^2-3^1-1 $$ it is suggested that, for $n>1$, we have: $$ a_n=3^{n-1}-\sum_{k=0}^{n-2}3^k $$ and you can verify that this result satisfies the given recursive definition.