Hows my proof look? enter image description here

Any feedback welcome

  • $\begingroup$ That is a correct use of induction. $\endgroup$ – Lepidopterist Dec 9 '11 at 21:09

Your essential argument is right. Some comments though:

  • Don't write things like $$\begin{align*}a&\leq b =\\ c&\leq d\end{align*}$$ when you want to indicate that you have produced $c$ from $a$, and $d$ from $b$. It is wrong; it makes no sense (in this context at least) to have an equation between two statements.
    Just put in a word of explanation, e.g. as follows: $$a\leq b$$ or equivalently, $\quad$ / $\quad$ hence,$\quad$ /$\quad$ and simplifying, $\quad$ $$c\leq d.$$

  • Your induction step is phrased incorrectly - you are not assuming that $7n+3\leq 2^n$ for all $n\geq 6$ - that's what you want to prove! If we prove that a claim $P$ is true assuming that $P$ is true, we have not really proven anything, have we?

    What you are supposed to assume that the the statement $$ 7n+3\leq 2^n$$ is true for all $6\leq n\leq k$, for some number $k$, and using this assumption, prove that the statement must also be true for $k+1$, i.e. $$ 7(k+1)+3\leq 2^{k+1}.$$ This is called "complete induction", or sometimes "strong induction". One is also allowed to assume only that the statement is true for $k$, and prove that it must then be true for $k+1$; this is also a valid inductive arugment. See here, and also my answer here.

    Note that it is all too common for books, professors, etc. to use the same letter for both the statement itself, and the proof by induction, which can lead to unnecessary confusion (even though it does not affect the veracity, of course). Under the setup I am proposing you follow, you would instead write "case $k$ $\implies$ case $k+1$".

  • "lie" should be "like"

  • $\begingroup$ This is why I post on SE, thanks for the tips :) $\endgroup$ – Matt Dec 9 '11 at 21:57

The idea is fine. You know what's going on. The exposition is not so fine. Some changes are needed.

Early on you write $7(6)+3 \le 2^6$, then a mysterious arrow, then $45 \le 64$. What you need to say that $7(6)+3=45$ and $2^6=64$, and therefore $7(6)+3 \le 2^6$. That little arrow is private language, but borrows a standard symbol for "implies." That is not what you mean.

Under 2a. you say assume case $n$ is true, and then write $7n+3 \le 2^n$ for all $n \ge 6$. That's saying you are assuming the result holds for all $n$. Of course, you don't intend to say that, so don't say it. The whole of 2a. is unnecessary.

Under 2b. it may be healthier to show that if the result holds when $n=k$, it holds when $n=k+1$. That may make it easier to keep in mind that you are assuming the result holds for a specific $n$, and that you are then dealing with the next one.

Don't use the equals sign for propositions. It is particularly disconcerting when it is used in combination with inequality signs.

Don't operate from the (presumed) inequality $7(n+1)+3 \le 2^{n+1}$. Manipulating equations or inequalities you are trying to prove is (sadly) encouraged in high school. In more complicated situations you will lose control of the logic. Of course you can do anything you like before writing down the proof.

Maybe give an introductory sentence that says suppose that $7k+3 \le 2^k$. We will show that $7(k+1)\le 2^{k+1}$.

Now I will use your $n$, not $k$. By the induction assumption, $7n+3\le 2^n$. Note that if $n \ge 6$, then $7<2^n$. Thus $$7(n+1)+3 =(7n+3)+7 \le 2^n+7 <2^n+2^n=2^{n+1}.$$ The point is to work from $7(n+1)+3$, not from the inequality $7(n+1)+3 \le 2^{n+1}$.

Towards the end, there is again that little arrow, which is not standard mathematical notation, at least not for what you mean.


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.