Solve the following

Given : A sequence $x_{0}, x_{1}, x_{2}, x_{3}, \ldots$ is defined by letting $x_{0}=5$ and $x_{k}=4+x_{k-1}$ for all natural number $k$.

Let $\mathrm{P}(n): x_{n}=5+4 n$ for all $n \in \mathbf{N}$.

Step I: For $n=0$,

$\mathrm{P}(0): x_{0}=5+4 \times 0=5$

So, it is true for $n=0$.

Step II : For $n=k$,

Let $\mathrm{P}(k): x_{k}=5+4 k$ be true for some $k \in \mathbf{N}$.

Step III : For $n=k+1$,

$\mathrm{P}(k+1): x_{k+1}=4+x_{k+1-1}$

$=4+x_{k}$

$=4+5+4 k$

$=5+4(k+1)$

So, it is also true for $n=k+1$.

Hence, $x_{n}=5+4 n$ for all $n \in \mathbf{N}$.