4
$\begingroup$

Example 1:

Prove by induction that $1+3+5+...+(2n-1)=n^2 \text{ for all } n \in \mathbb{N}....(*)$

Proof:

Step 1: For $n=1$, left-side we have $(2(1)-1) = 1$. Right-side we have $(1)^2 = 1$.

Step 2: Suppose (*) is true for some $n=k \in \mathbb{N}$ that is $$1+3+5+...+(2k-1)=k^2$$

Step 3: Prove that (*) holds true for $n=k \in \mathbb{N}$ that is (adding $(2k+1)$ to both sides) $$1+3+5+...+(2k-1)+(2k+1)=(k)^2+(2k+1)$$

we have

enter image description here

which shows both sides are equal?

but you can do this to several number of problems....

Example 2:

Prove by induction that $1^3+2^3+...+n^3=(1+2+...+n)^2 \text{ for all } n \in \mathbb{N}....(*)$

Proof:

Step 1: For $n=1$, left-side we have $1^3 = 1$. Right-side we have $(1)^2 = 1$. Which shows both sides are true.

Step 2: Suppose (*) is true for some $n=k \in \mathbb{N}$ that is $$1^3+2^3+...+k^3=(1+2+...+k)^2$$

Step 3: Prove that (*) holds true for $n=k \in \mathbb{N}$ that is (adding $(k+1)^3$ to both sides) $$1^3+2^3+...+k^3 + (k+1)^3=(1+2+...+k)^2 + (k+1)^3$$

we have

enter image description here

which shows both sides are equal again...

what am I fundamentally doing wrong?

$\endgroup$
  • 2
    $\begingroup$ Note that $k^2 + (2k+1) = (k+1)^2$. In the other one, after fixing a typo (you wrote $n$ where $k$ belongs), you still need to show that $$(1 + 2 + \dotsc + k)^2 + (k+1)^3 = (1 + 2 + \dotsc + k + (k+1))^2.$$ $\endgroup$ – Daniel Fischer Sep 6 '15 at 20:49
  • $\begingroup$ In example one you want the right hand side to be $(k+1)^2$. As you note, the left hand side is trivially $k^2+2k+1$, but that is not the issue.. $\endgroup$ – Paul Sep 6 '15 at 20:53
3
$\begingroup$

What am I fundamentally doing wrong?

There is really only one thing I can tell you are doing wrong, but it is not such a trivial point. Suppose your statement to prove is $S(n)$; the inductive hypothesis will be $S(k)$ (where this will be assumed to be true for some fixed $k\geq ?$), and you will then be trying to show that $S(k)\to S(k+1)$, where you work from the left-hand side of $S(k+1)$ to the right-hand side of $S(k+1)$. The problem is that you are not working to the right-hand side of $S(k+1)$. You simply throw in your extra summand in both examples but do not actually work towards coaxing the right-hand side of $S(k+1)$ out of the left-hand side of $S(k+1)$. To illustrate specifically what I am talking about, I'll show you via your first example (the same applies for your second example though).


Example 1: Here you are trying to establish that $$ S(n) : \sum_{i=1}^n(2i-1)=n^2. $$ Your inductive hypothesis is $$ S(k) : \sum_{i=1}^k(2i-1)=k^2. $$ Now, you need to show that $$ S(k+1) : \sum_{i=1}^{k+1}(2i-1)=(k+1)^2 $$ follows from $S(k)$. What you are doing is simply slapping on the extra $2k+1$ term on the left- and right-hand side of $S(k+1)$. This may not be seen as technically wrong in that it will ruin your proof, but it is very sloppy and should be avoided. In a simple summation problem like this, there's not much of an issue, but it's a bad habit to cultivate (the bad habit being not formulating the inductive proof very clearly). Here, we clearly have that $k^2+2k+1=(k+1)^2$, but what happens when you have something much more complicated? You end up with an unnecessarily complicated proof that is sloppy, unclear, etc. Here is how I would write up your proof:

Claim: For $n\geq 1$, let $S(n)$ denote the proposition $$ S(n) : \sum_{i=1}^n(2i-1)=n^2. $$

Base case ($n=1$): $S(1)$ says that $2(1)-1=1=1^1$, and this is true.

Inductive step: Assume that $$ S(k) : \sum_{i=1}^k(2i-1)=k^2 $$ is true for some fixed $k\geq1$. To be shown is that $$ S(k+1) : \sum_{i=1}^{k+1}(2i-1)=(k+1)^2 $$ follows. Beginning with the left-hand side of $S(k+1)$, \begin{align} \sum_{i=1}^{k+1}(2i-1)&= \sum_{i=1}^k(2i-1)+2(k+1)-1\tag{by $\Sigma$-defn.}\\[0.5em] &= k^2+(2k+1)\tag{by $S(k)$}\\[0.5em] &= (k+1)^2\tag{factor} \end{align} we end up at the right-hand side of $S(k+1)$, completing the inductive step.

By mathematical induction, the proposition $S(n)$ is true for all $n\geq 1$. $\blacksquare$


Finally, you may find this post helpful in regards to writing clear induction proofs.

$\endgroup$
4
$\begingroup$

The problem is that you used the Step 2 too many times :

I'll explain it for the first example :

So you know that $$1+3+\ldots +(2k-1)=k^2$$ . Now add $2k+1$ (as you did) :

$$1+3+\ldots+(2k-1)+(2k+1)=k^2+2k+1$$ this is already true because you assumed it . You don't need to prove it . What you need to really prove is that : $$1+3+\ldots+(2k+1)=(k+1)^2$$ for the inductive step to follow . But you already known that the sum is $k^2+2k+1$ so all you need to prove is that :

$$k^2+2k+1=(k+1)^2$$ which should be obvious .

$\endgroup$
  • $\begingroup$ Thank you for that, I have upvoted your answer $\endgroup$ – lucidgold Sep 7 '15 at 1:43
4
$\begingroup$

In Step 3 of the second example, you write "Prove that (*) holds true for $n = k \in N$", but that should be $n = k + 1$.

I find it useful in proofs like this to write down something I call $P(n)$, the proposition that I want to prove, which is typically meant to be true for every integer $n$. In your example 3, $P(n)$ is the statement

$$ 1^3+2^3+...+n^3=(1+2+...+n)^2 $$ That means that $P(1)$ is the statement $$ 1^3=(1)^2 $$ and $P(2)$ is the statement $$ 1^3 + 2^3=(1+2)^2 $$ and so on.

Now you can say this:

I'm going to assume that for some $k \in \mathbb N$, $P(k)$ is true, i.e., that $$ 1^3+2^3+...+k^3=(1+2+...+k)^2 $$ And using only algebraic manipulation, I'll use this to establish that $P(k+1)$ is true, i.e., that $$ 1^3+2^3+...+k^3 + (k+1)^3=(1+2+...+k + (k+1))^2. $$

Now you have a starting point and a clear goal.

I'd say, at this point:

From the hypothesis, we have $$ 1^3+2^3+...+k^3=(1+2+...+k)^2 $$ Adding $(k+1)^3$ to each side, we get $$ 1^3+2^3+...+k^3+ (k+1)^3=(1+2+...+k)^2 + (k+1)^3 $$ To finish the proof, we have to show that the right hand side is the same as $(1 + 2 + \ldots + (k+1))^2$. To do so, let's look at the difference between these two, \begin{align} S &= (1+2+...+k)^2 + (k+1)^3 - ((1+2+...+k+(k+1))^2) \end{align} If we can show $S = 0$, we're done. Well, \begin{align} S &= (1+2+...+k)^2 + (k+1)^3 - ((1+2+...+k+(k+1))^2)\\ &= (1+2+...+k)^2 - (1+2+...+k+(k+1))^2 + (k+1)^3 \end{align} The first two terms look like $A^2 - B^2 = (A-B)(A+B)$, so \begin{align} S &= (1 + 2 + \ldots + k)^2 - (1 + 2 + \ldots + k+(k+1))^2 + (k+1)^3 \\ &= ((1 + 2 + \ldots + k) - (1 + 2 + \ldots + k+(k+1)))\cdot((1 + 2 + \ldots + k) + (1 + 2 + \ldots + k + (k+1))) + (k+1)^3 \\ &= ((1 + 2 + \ldots + k) - (1 + 2 + \ldots + k +(k+1)))\cdot((1 + 2 + \ldots + k) + (1 + 2 + \ldots + k + (k+1))) + (k+1)^3 \\ &= -(k+1)\cdot(2 (1 + 2 + \ldots + k) + (k+1)) + (k+1)^3 \\ &= -(k+1)\cdot(2 \frac{k(k+1)}{2} + (k+1)) + (k+1)^3 \\ &= -(k+1)\cdot( k(k+1) + (k+1)) + (k+1)^3 \\ &= -(k+1)\cdot( k(k+1) + 1\cdot(k+1)) + (k+1)^3 \\ &= -(k+1)\cdot( (k+1)(k+1) ) + (k+1)^3 \\ &= -(k+1)^3 + (k+1)^3 \\ &= 0. \end{align}

$\endgroup$
  • $\begingroup$ Very nice, I have upvoted your answer $\endgroup$ – lucidgold Sep 7 '15 at 1:43

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.