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!
 A: For 1): We have to provve that $$(n+1)^2>3(n+1)+1$$ if $$n^2>3n+1$$
We have $$(n+1-1)^2=(n+1)^2-2(n+1)+1>3n+1$$ This is 
$$(n+1)^2>3n+2n+1=5n+1>3(n+1)+1$$ if >$$n\geq 2$$ For $n=1$ is the inequality not true, since $$1\ne 3+1$$
For 2). Note that $$n^3-n=(n-1)n(n+1)$$
A: 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.
A: For 1, the expression $3(k+1)+1<(k+1)^2$ is what you want to deduce based on the known fact that $3k+1<k^2$. So using this fact you get that $3(k+1)+1<k^2+3$ and since $k^2+3<k^2+2k+1=(k+1)^2$ for all $k\geqslant 4$ we get what we wanted.
For 2, try to follow the same type of argument yourself. The case $n=1$ is done because $0$ is divisible by $6$. Then based on the fact that $k^3-k$ is divisible by $6$, expand the expression $(k+1)^3-(k+1)$ and obtain the result using the induction hypothesis. Hint: it is sufficient to check that this expression is divisible by $2$ and by $3$ separately.
A: Suppose $k^2>3k+1$ and $k\ge4$; then
\begin{align}
(k+1)^2
&=k^2+2k+1\\[4px]
&>(3k+1)+2k+1\\[4px]
&=5k+2\\[4px]
&=3(k+1)+2k-1\\[4px]
&> 3(k+1)+1
\end{align}
The tricky part is to split $5k+2$ as $3(k+1)+(2k-1)$, but you know you want to find $3(k+1)$ in the right hand side.
The hypothesis $k\ge4$ is used for concluding that $2k-1>1$.

For the second part, consider
\begin{align}
(k+1)^3-(k+1)
&=k^3+3k^2+3k+1-k-1\\[4px]
&=(k^3-k)+3(k^2+k)
\end{align}
Then $k^3-k$ is divisible by $6$ by the induction hypothesis, whereas $3(k^2+k)$ is divisible by $3$ and by $2$.
A: Below I explain how to intuitively derive these inductive proofs in a very simple uniform way.

$(1)\ $ To intuitively prove $f(n) = n^2-3n-1 > 0$ for $n\ge 4$ is easy using the following Lemma showing that a discrete increasing function stays greater than its intitial value. Applying it $\,f(n+1)-f(n) = 2(n-1) > 0 $ for $\,n \ge 4\,$ so $\,f(n) > f(4) = 3$ for $\,n\ge 5.\ \ $ QED

Lemma $\ $ If $f(n+1) > f(n)\,$ for $n\ge a$ then $f(n) > f(a)$ for $n\ge a+1$
Proof $\ $ The base case  $n = a+1$ it true by hypothesis and the induction step is clear $$\underbrace{f(n)>f(a)}_{\large P(n)}\,\Rightarrow\, f(n+1)>f(n)>f(a)\,\Rightarrow\, \underbrace{f(n+1)>f(a)}_{\large P(n+1)}$$ 

$(2)\ $ Similarly, to intuitively prove $\,f(n) = n^3-n\equiv 0\pmod{6}$ is easy using the following result showing that an unchanging discrete function stays equal to its initial value. Applying it $\,f(n+1)-f(n)\equiv 3(n^2+n) \equiv 0$ by $\,2\mid n^2+n,\,$ so $\,f(n)\equiv f(0)\equiv 0\,$ for $\,n\ge 0.\ \ $ QED

Lemma $\ $ If $\,f(n+1) \equiv f(n)\,$ for $\,n\ge a$ then $\,f(n) \equiv f(a)\,$ for $\,n\ge a$
Proof $\ $ Very similar to that of prior Lemma. Prove it!

Remark $\ $ Both methods are special cases of telescopic induction. You can find much further discussion of such in my prior posts on this topic, including many worked examples.
