3
$\begingroup$

I am working on induction problems to prep for Real Analysis for the fall semester. I wanted proof verification and editing suggestions for part (a), and assistance understanding part (b). For part (b), the portion that has the additional indentation is where I am unclear.

The principle of mathematical induction can be extended as follows. A list $P_m, >P_{m+1}, \cdots$ of propositions is true provided (i) $P_m$ is true, (ii) >$P_{n+1}$ is true whenever $P_n$ is true and $n \geq m$.

(a) Prove $n^2 > n + 1$ for all integers $n \geq 2$.

Assume for $P_n$: $n^2 > n + 1$, for all integers $n \geq 2$. Observe for $P _2$:

$P_2: 2^2=4 > 2+1 = 3$,

thus the basis step holds. Now, let $n=k$ such that $k^2 > k + 1$, and assume this also holds. We now consider the case $P_{k+1} : (k+1)^2 > (k+1) + 1$.

Observe:

$(k+1)^2 = k^2 + 2k + 1$

= $k(k+2) + 1$

Clearly, $k(k+2)+1$ must be greater than $(k+1)+1$. Thus, by the principle of mathematical induction, the case holds for all $n \geq 2$.

*I am aware that part (a) does not require induction to prove, but the book problem suggests doing so...


(b) Prove $n! > n^2$ for all integers $n \geq 4$.

Assume for $P_n$: $n!>n^2$ for all integers $n \geq 4$. Observe for $P_4$:

$P_4: 24 = 4! > 16 = 4^2$,

thus the basis step holds. Let $n=k$ such that $k! > k^2 $, and assume this also holds. We now consider the case $P_{k+1} : (k+1)! > (k+1)^2$. Observe:

$(k+1)! = (k+1)k!$

$> (k+1)k^2$

$= k^3 + k^2$

$> k^2 + 2k + 1$

$= (k + 1)^2$

I was able to write some of this on my own, and I used my book + internet to help me figure out how to write this out. First, I am not clear why we are adding $(k+1)$ to the right hand side (the $k^2$) side of the equation (or what that's allowed, really). Also, I'm not clear on the jump from $k^3+k^2>k^2 + 2k + 1$.

Additionally, while looking around MSE, I have noticed many people talk about induction with LHS and RHS notation. I have not seen this in any books--would someone be able to explain using that method as a form of bookkeeping, or be able to suggest a site or stack that could do that?

$\endgroup$
  • $\begingroup$ To show $(k + 1)k^2 > (k + 1)^2$, evaluate the ratio between these two as I did in my proof. $\endgroup$ – Zhanxiong Aug 12 '15 at 4:23
2
$\begingroup$

Note: Your question should really be two questions since they're completely distinct and separate. You are simply trying to cover too much for one single question on this site, but I'll help with what I can.

Before addressing both parts of your question, I would encourage you to read the following three posts because I think they would go a long way in helping you with induction proofs in general.

  1. How to write a clear induction proof.

  2. The difference between weak and strong induction.

  3. Use of LHS/RHS notation or terminology in an induction answer.

Now on to your question(s).

Part (a): Your write-up here is really struggling in a number of ways. I'm going to be straight with you--your statement of strong induction is sloppy (you don't actually need strong induction even if you do use an inductive argument which is why I included (2) above) and your inductive "proof" never even uses the inductive hypothesis. See (1) above for how to actually write a clear induction proof; this will more or less force you to understand how the proof actually works, where you use the inductive hypothesis, etc. Also, as Hirshy notes, you actually assume what you are trying to prove (you do this again in part (b)). Regardless, the following is one way you could structure the main part of your induction proof for part (a): \begin{align} (k+1)^2&= \color{blue}{k^2}+2k+1\tag{expand}\\[0.5em] &\color{blue}{> (k+1)}+2k+1\tag{by inductive hypothesis}\\[0.5em] &= 3k+2\tag{simplify}\\[0.5em] &> k+2\tag{since $k\geq 2$}\\[0.5em] &= (k+1)+1.\tag{simplify} \end{align} Did you see how that worked? Can you see how the inductive hypothesis is used in the part highlighted with $\color{blue}{\mathrm{blue}}$?

Part (b): The part you have indented is actually not too bad at all when you actually write out what is happening and why at each step; nonetheless, you still need to clean up the beginning, as you are again assuming what you are trying to prove. The goal here is to move from the left-hand side (LHS) of the statement $P_{n+1}$ to the right-hand side (RHS) of $P_{n+1}$. To that end, note the following (the indented steps have explanatory notes in the margin now): \begin{align} (k+1)! &= (k+1)k!\tag{by definition}\\[0.5em] &> (k+1)k^2\tag{by induction hypothesis}\\[0.5em] &= k^3+k^2\tag{expand}\\[0.5em] &> k^2+2k+1\tag{since $k\geq 4$}\\[0.5em] &= (k+1)^2.\tag{factor} \end{align} Can you see how all of that worked?

$\endgroup$
  • $\begingroup$ Thanks, I will look at the resources you have provided. As for assuming what I am trying to prove, that style of statement was a sort of "house rule" we had in our class over the summer (Intro to Abstract). The prof tried to explain it as though we weren't proving the general case, we were proving the $nth$ case. But, if this is considered poorly written, then I will consider that for my next class. $\endgroup$ – Mr. Meeseeks Aug 12 '15 at 5:20
  • 1
    $\begingroup$ Nice work here, especially on the linked questions! $\endgroup$ – Hirshy Aug 12 '15 at 5:20
  • $\begingroup$ @DanielW.Farlow Your notes in the margin are identical to the ones I have in my notes (I did not include them in my post), for part (b). I still don't have anything click for me going from $=k^3 + k^2$ to $k^2 + 2k +1$ since $k \geq 4$. But, I will look at your resources and see what I can come up with. $\endgroup$ – Mr. Meeseeks Aug 12 '15 at 5:22
  • $\begingroup$ @kallixti That phraseology is really kind of a "sticky point"--that is, depending on the context in which you first encountered induction, it is possible the prof was largely trying to provide the scaffolding for understanding induction proofs in general in a sense (if that is at all reasonable). It's unfortunate that phrasing is used sometimes though because it really does muddle the waters (as it has here) and can serve as an educational impediment in the future. $\endgroup$ – Daniel W. Farlow Aug 12 '15 at 5:22
  • $\begingroup$ @Hirshy Thanks for the kind words! $\endgroup$ – Daniel W. Farlow Aug 12 '15 at 5:23
1
$\begingroup$

You don't actually need induction here.

If $n \geq 4$, then $$\frac{n!}{n^2} = \frac{n \times (n - 1) \times \cdots \times 1}{n \times n} = \frac{(n - 1) \times (n - 2)}{n} \times (n - 3)! \geq 1 \times 1 = 1$$ because $$(n - 1) \times (n - 2) - n = n^2 - 4n + 2 = n(n - 4) + 2 \geq 2 > 0.$$

$\endgroup$
  • $\begingroup$ Yeah, but the question in the text book says to use induction (as this is the induction chapter), so I have to use induction to figure it out (sorry, this is stated in my original question, perhaps not as clearly as it could be). Thanks, however! I like this proof... it's simple. $\endgroup$ – Mr. Meeseeks Aug 12 '15 at 4:20
  • $\begingroup$ Of course you can modify this proof to your induction framework, give it a try. $\endgroup$ – Zhanxiong Aug 12 '15 at 4:21
1
$\begingroup$

To get last part of (b) use problem (a) . Note that $K^3+K^2=K^2(K+1)>(K+1)(K+1)=(k+1)^2$(using part a)

$\endgroup$
1
$\begingroup$

Regarding (a): even if your book tells you it should be done by induction, it is not needed here and IMO does nothing good to understand the principle of induction. When you're starting to learn maths on a higher level, induction often is one of the first and easiest methods of proving and thus is also used to learn the strict formality of a proof. This is missing in the proof for a), as the key step, using the induction hypothesis is never executed. Further I wouldn't "assume $n^2>n+1$ for all integers $n>^2$", as this is what you're trying to proof, but that might be some stilistic problem; just check your wording on this and compare with the notation and wording in your book.

Now moving on to (b):

in the inductive step you may (and should) use the induction hypothesis. For this question you assume, that $k!>k^2$ has already been proven up to some $k\in\mathbb N$. Thus you get: \begin{align*}(k+1)!&=k!\cdot (k+1) \tag{definition of $k!$} \\ &>k^2\cdot (k+1) \tag{induction hypothesis}\end{align*} It is also important to note, that $(k+1)>0$ for the inequality to hold. Now, where do we stand on solving the question? We have $$(k+1)!>k^2\cdot(k+1),$$ we want to have $$(k+1)!>(k+1)^2,$$ so now we have to manipulate $k^2\cdot(k+1)$ to get there. For this we will use question (a): \begin{align*}k^2\cdot (k+1)&>(k+1)\cdot (k+1) \tag{as $k^2>k+1$} \\ &=(k+1)^2\end{align*}

This completes the proof via mathematical induction.

In general, those first tasks on induction are very similar to one another and once you're used to them don't really count as "proving" something but seem more like simple calculating. This doesn't mean, that induction will always be easy and as structured as this question, e.g.:

Let $\mathcal{V}$ be a vector space over a field $\mathbb F$ and let $s\in\mathbb N$. If $\mathbb F$ is finite, further assume $s\leq |\mathbb F|$. Show: if $\mathcal U_1,\dots, \mathcal U_s$ are subspaces of $\mathcal V$ with $U_i\neq \mathcal V$, then $\mathcal V\neq \bigcup\limits_{i=1}^{s} \mathcal U_i$.

This can be proven with mathematical induction. Of course you shouldn't take on this question yet (for one because it is quite difficult for beginners, but it also is dealing with concepts of linear algebra and not real analysis), it just serves as an example that proofs by induction might differ from the well-structured, "always the same" questions you encounter at the beginning of your studies.

Feel free to ask questions, if something remains unclear!

$\endgroup$
  • $\begingroup$ There are so many things wrong with part (a) I truly wonder how someone could assign that as an induction problem: 1) induction is not needed, 2) strong induction is certainly not needed, etc etc. OP has good answers here though so hopefully it will all gel fairly soon. $\endgroup$ – Daniel W. Farlow Aug 12 '15 at 5:15

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.