# Recursive Sequence Proof

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}$.

• By definition, $a_k=3k+1$ and $a_{k-1}=3(k-1)+1$. You are supposed to show that $(3k+1)-(3(k-1)+1)=3$. That is not hard. – André Nicolas Nov 14 '13 at 2:10
• I just got confused because we're supposed to be doing this via proof by induction and the basis was eluding me. Thank you. – Jay3 Nov 14 '13 at 2:14

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$.