Help with proof by induction and divisibility

Question

I have a question about induction (I'm a little fuzzy on it).

1. Prove $3n+1<n^2$ for all integers $n\geq 4$.
2. 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!

Answer 1

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

Answer 2

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

Answer 3

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.

Answer 4

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.

Answer 5

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.