I'm trying to learn about recursion, first with this exercise:
Find the explicit formula for the succession $$x_0=2, x_{n+1} = 5x_n$$
So, from what I've seen, I should test a bit. I see that the formula is pretty much the previous value by $5$:
$$x_0=2$$
$$x_1=5\cdot2$$
$$x_2=5\cdot(5\cdot 2)$$
$$x_3=5\cdot(5\cdot(5\cdot2))$$
It seems to me that a formula would be
$$x_n=5^n\cdot2$$
Now I have to prove it by induction, according to the exercise.
Test for $n=0$:
$$x_0 = 5^0\cdot2$$
$$2 = 2$$
I want to prove that it holds for $n + 1$, that is:
$$x_{n+1} = 5^{n+1}\cdot 2$$
Let's see:
$$x_{n+1}$$
This is where I'm getting a bit stuck, I had thought that the previous is equivalent to this:
$$x_n+5^{n+1}\cdot2$$
But that doesn't make any sense, because that would definitely be not equal to what I want to prove.
How should I had proceeded from this point?
You want to prove that $x_{n+1} = 5^{n+1} \cdot 2$. The induction hypothesis that you can use for this is $x_n = 5^n \cdot 2$. Now apply the recurrence relation and find $x_{n+1} = 5 x_n = 5 (5^n \cdot 2) = 5^{n+1} \cdot 2$.