Induction proof: Let $a_0=1,$ $a_{n+1}=10a_n-3$, Find an explicit formula for $a_n$

Question

Let $a_0=1,$ $a_{n+1}=10a_n-3$

Find an explicit formula for $a_n$

I took this from a book called "A Walk Through Combinatorics" that I found online to practise combinatorics and induction proofs.

So, supposedly, I'm to try and guess the formula and then try to prove with it with an induction, so this is what I found:

$$a_1=10*1-3=7$$ $$a_2=10*7-3=67$$ $$a_3=10*67-3=667$$ $$....$$

So it looks like a function that adds a 6 from the left side each time but I have no idea how can I formulate it into an explicit formula...

Answer 1

You can express the number$$\overbrace{66\ldots66}^{n-1\text{ times}}7$$as$$7+\sum_{k=1}^{n-1}6\times10^k.$$So, your conjecture is$$(\forall n\in\mathbb{N}):a_n=7+\sum_{k=1}^{n-1}6\times10^k.$$This is clearly true if $n=1$. Now, if $n\in\mathbb N$ is such that $a_n=7+\sum_{k=1}^{n-1}6\times10^k$, then\begin{align}a_{n+1}&=10a_n-3\\&=70-3+\sum_{k=1}^{n-1}6\times10^{k+1}\\&=67+\sum_{k=2}^n6\times10^k\\&=7+60+\sum_{k=2}^n6\times10^k\\&=7+\sum_{k=1}^n6\times10^k.\end{align}

Answer 2

$$a_{n+1}-\frac{1}{3}=10(a_{n}-\frac{1}{3}).$$ $a_0-\frac{1}{3}=\frac{2}{3}$, so $$a_n-\frac{1}{3}=\frac{2}{3}(10)^n,n=0,1,\cdots,$$ and $$a_n=\frac{1}{3}+\frac{2}{3}(10)^n,n=0,1,\cdots.$$

Answer 3

Let $a_m=B_m+cm+d$

$$\implies3=10a_n-a_{n+1}$$

$$=10(B_n+cn+d)-(B_{n+1}+cn+c+d)=10B_n-B_{n+1}+9cn+9d-c$$

Choose $c=0, 9d-c=3$ to get $B_{n+1}=10B_n$

Answer 4

hint: Observe that $a_n - a_{n-1} = 10(a_{n-1} - a_{n-2})$. This means $b_n = 10b_{n-1}$ with $b_n = a_n - a_{n-1}$. You find $b_n$ and then telescope to find $a_n$

Answer 5

So it looks like a function that adds a 6 from the left side each time but I have no idea how can I formulate it into an explicit formula...

Alternatively phrased, it adds $6\times 10$, then $6 \times 100$, then $6 \times 1000$, ...

If you're not familiar with the geometric series $a + ar + ar^2 + \cdots + ar^n$ then it's worth learning about, because it comes up in other contexts too. The standard evaluation with proof is: $$a + ar + \cdots + ar^n = a + r(a + ar + \cdots + ar^n) - ar^{n+1}$$so rearranging $$a + ar + \cdots + ar^n = a \frac{r^{n+1} - 1}{r - 1}$$