<s>[INST] Help with proof by induction and divisibility I have a question about induction (I'm a little fuzzy on it). 


*

*Prove $3n+1<n^2$ for all integers $n\geq 4$.

*Assume $k^2+k$ is an even integer for any $k\in\mathbb{Z}$. Prove $n^3-n$ is divisible by 6 for all $n\in\mathbb{N}$.


For 1, I have: Base Case: Let $n=4$. Evaluate the inequality, returning $13<16$. Thus, the base case is valid. Induction step: Suppose that, given $k\geq 4$, $3k+1<k^2$ is true for $n=k$. Then, $3(k+1)+1<(k+1)^2$. I am stuck from here.
For 2, I have: Base case: Let $n=1$ (the first natural number in this case). Evaluate the expression $n^3-n$ as $0$. Now I am stuck. Am I supposed to evaluate at $n=2$? Induction step: take $k$ to be true such that $k^3-k$ is divisible by 6 (am I allowed to do this?). Then, $(k+1)^3-(k+1)$, or $k^3+3k^2+3k+1-(k+1)$, or $(k^3-k)+3(k^2+k)$. Now I am stuck.
Help is appreciated!
 [/INST] 1)
$3(k+1)+1 = 3k + 4$ and $3k+1 < k^2$ so $3k + 4 < k^2 +3$.
And $(k+1)^2 = k^2 + 2k + 1$.  ANd $k\ge 4$ so $2k + 1 \ge 9$.  
So $k^2 + 3 < k^2 + 9 \le k^2 + 2k +1 = (k+1)^2$
2)
$n^3 - n = 0$ if $n = 1$.  And $0$ is divisible by $6$ (because $0 = 6*0$) so, no, you are not stuck.
But if you want to do $n =2$ for backup go ahead.  $n^3 -n = 2^3 - 2=6$ and $6$ is divisible by $6$.
And for the induction step.  If $k^3 - k$ is divisible by $6$ then $(k+1)^3 - (k+1) = k^3 + 3k^2 + 3k + 1 - k - 1 = (k^3 - k) + 3(k^2 + k)$.  You know that $k^3 -k$ is divisible by $6$ so all you have to do is prove $3(k^2 + k)$ is divisible by $6$.  It's divisible by $3$ so all you have to do is prove $k^2 + k$  is even. Which you can do be induction if you want.  Or but taking cases if $k$ is even or odd.
</s>