Induction profe with geometrical cycle

Question

I have an equation:

$$x(n+1)=5x(n)+4\\x(0)=0$$

For my task I need to provide simple equation for $x(n)$, so I go for this method:

1. I make some changes in equation: $$x(n+1)=5x(n)+5-1\\ x(n+1)=5(x(n)+1)-1$$

2. I use temp function $$y(n)=x(n)+1\\ x(n+1)=5y(n)-1\\ 5y(n)=x(n+1)+1$$

3. I calculate first few values for $y(n)$ for $n=0$: $$5y(0)=x(1)+1=1$$ {$x(1)=4$, from previous equation} for $n=1$: $$5y(1)=x(2)+1=5$$ for $n=2$: $$5y(2)=x(3)+1=25$$

So I see that $y(n)$ is geometrical cycle, so from theory of geometrical cycle:

• equation for $n+1$ element will be: $$y(n+1)=y(n)\cdot q - q=5,$$ because every next element is $5$ times bigger so: $$y(n+1)=y(n)\cdot5$$
• equation for n element will be y(n)=y(0)*q^(n-1) {y(0) was 5}, so y(n)=5^n

But this is something I guess on base of few values so I need to prove: $y(n)=5^n$

Induction - step 1 - for $n=1$ $$y(1)=5^1\\ L=5\\ R=5\\ L=R$$ It's correct

Induction - step 2 - for $n=k$ $$y(k)=5^k$$

Induction - step 3 - for $n=k+1$ $$y(k+1)=5^(k+1)$$

$$L=y(k+1)\text{ (from equation for } n+1\text{-th element }y(k+1)=y(k)\cdot 5\text{)}\\ L=5y(k)\\ R=5^(k+1)\\ \text{Both sides are divided by 5}\\ L=y(k)\\ R=5^k\\ L=R$$

And it looks fine for me but, last time I solve this it was wrong because "I tried to prove one thing using this same thing" which is wrong, and I am not sure if this one is correct, cna I use first step in "step 3"?

p.s. sorry for my english :)

EDIT I made some changes according to user160738 advices, please can you check is it correct now? Link to PDF

Answer 1

I think a big gap in your arguments is that in your step 3 you observed some values of $y(n)$ and conjectured that $y(n)$ is a geometric sequence.

Then you assumed it to be geometric sequence and $y(n)$ has to have certain expression when you assumed it to be in that form.

So you assumed what you wanted prove and proved it again (circling argument).

Your induction step seems fine, so I will just add some clarification for your conjecture:

In first step you found that

$$ x(n+1)=5(x(n)+1)-1$$

Let's define $y(n)$ as you defined it to be.

Then $$y(n)=x(n)+1$$

and we have

$$ x(n+1)=5(x(n)+1)-1 \implies x(n+1)+1=5(x(n)+1) \implies y(n+1)=5y(n)$$

Now the answer follows immediately using induction

Answer 2

At this moment I am too lazy to have a good look at your work, so just an advice to make things easyer. If we just write down the $x_n$ then we see:

• $x_0=0$
• $x_1=4$
• $x_2=5.4+4$
• $x_3=5.5.4+5.4+4$
• $x_4=5.5.5.4+5.5.4+5.4+4$

et cetera.

Don't you recognize something a nice pattern here? Based on it you can find an expression of $x_n$ and you can make things complete by proving that $x_{n+1}=5.x_n+4$ by means of induction.

Answer 3

Equations like this are best solved by rewriting them as difference equations: $$ a_k = 5 a_{k-1} +4\\ a_{k-1} = 5 a_{k-2} +4\\ \Delta a_k = 5 \Delta a_{k-1} = 5^2 \Delta a_{k-2} = \ldots 5^{k-1} \Delta a_1 $$ You know the boundary value, so you need to make one little last step to get the solution.

Answer 4

look for a particular solution of $x(n+1)= 5x(n) + 4$ in the form $x(n) = A.$ $A$ is determined by $A = 5A + 4$ so $A = -1$ now the solution to the homogeneous equation $x(n+1) = 5x(n)$ is $x(n) = C5^n$ and the general solution is $$x(n) = C5^n -1$$ and $C$ gets fixed by requiring $x(0) = 0$ which give you $C=1.$ so the solution is $$x(n) = 5^n - 1$$