1
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – André Nicolas Nov 14 '13 at 2:10
  • $\begingroup$ I just got confused because we're supposed to be doing this via proof by induction and the basis was eluding me. Thank you. $\endgroup$ – Jay3 Nov 14 '13 at 2:14
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.