Recursive Sequence Proof

Question

Take the function defined by $a_n= 3n + 1$, for all $n \in \mathbb{N} \geq 0$. Show that this sequence satisfies the recurrence relation $ a_k = a_{k-1} + 3$ $\forall k \in \mathbb{Z}, k \geq 1$. My main problem is finding the basis because no conditions were assigned to $a_{k-1}$.

Answer 1

Since $a_n=3n+1$ for all $n\geq0$, we can see that $a_0=1$ and $a_1=4$. Using the recurrence relation $a_k=a_{k-1}+3$ for all $k\geq1$ we see that $a_1=4$ when $a_0=1$. Assume that $a_l=3l+1$ for some arbitrary positive integer $l$. We must show that $a_{l+1}=a_l+3=3l+4$. Consider $a_l+3$, using our induction hypothesis we obtain $a_l+3=(3l+1)+3=3l+4$. Thus by the Principle of Mathematical Induction $a_n=3n+1$ for all $n\geq0$ is a solution to the recurrence relation $a_k=a_{k-1}+3$ for all $k\geq 1$.