1

I am retaking a discrete math class and my new teacher is teaching mathematical induction differently than my old teacher. I really like the way I first learned it because I think it is more formal and I understand it better. But my current teacher says it is wrong, but I know it’s not. I’m fuming and desperately want to prove him wrong. Can you please help me prove that this method is correct?

Example:

Use mathematical induction to prove $\sum_{k=1}^{n} (2k-1) = n^2$

Base Case: $$ \sum_{k=1}^{1} (2k -1) = 1^2 $$ $$ 2(1)-1 = 1$$ $$ 1=1 $$

Inductive hypothesis: Assume $$\sum_{k=1}^{n} (2k-1) = n^2$$

Inductive step: Show the equation holds true for the $n+1$ case.

$$\sum_{k=1}^{n+1} (2k-1) \stackrel?= (n+1)^2$$ $$2(n+1)-1 + \sum_{k=1}^{n} (2k-1) \stackrel?= (n+1)^2$$ $$(2n+1) + \sum_{k=1}^{n} 2k -1 \stackrel?= n^2 + (2n+1)$$ $$\sum_{k=1}^{n} 2k-1 = n^2$$

Therefore if the $n+1$ case holds equivalence from the $n$ case (we can let n=1 because we know that is true), then it must hold true for the $n+2$ case, the $n+3$ case, and so on. But my professor says it’s wrong because I’m changing both sides at once. Can someone help me prove this process?

Ryan
  • 1,200
  • I don't understand your use of $=$ and $\stackrel?=$ throughout. You have not written any implications between your logical statements. Are you implying that every statement you have written is equivalent? – Peter Foreman Mar 06 '20 at 00:46
  • @PeterForeman when we test the n+1 case, we don’t know if it is equivalent yet, that is what we’re trying to find out. So I would find it incorrect to use a = if we don’t know. I use the ?= to say “is this equivalent?” Then once we can reduce it to a form that is recognizable as equivalent, then we can say it does indeed = – Ryan Mar 06 '20 at 00:48

2 Answers2

2

Instead of an equals sign with a question mark showing what you want to prove, you should start with one side of the equation and produce the other. Given your assumption, you can then write $$\sum_{k=1}^{n+1}2k-1=\left(\sum_{k=1}^{n}2k-1\right)+2n+1\\ =n^2+2n+1\\ =(n+1)^2$$ You should not go from what you hope to prove to what you know, because some steps may not be reversible. Here they are, so you can just do the steps in reverse order. You should either start with an equation you know to be true, like your last, and finish with what you want to prove, or start with an expression and compute the other side of the equation. I did the second of these above.

Ross Millikan
  • 374,822
  • Thank you! This is a much better way of expressing what I wanted. This is much more elegant and uses proper notation. I like the idea of replacing the expression in parenthesis with another equivalent expression from our given assumptions – Ryan Mar 06 '20 at 00:55
  • 1
    It is very common in an induction argument to break a sum into the piece that is the inductive hypothesis and a piece that is the new part. You then use the inductive hypothesis, as I did from line 1 to line 2, and combine it with the new part to get the desired result. – Ross Millikan Mar 06 '20 at 01:59
0

Near the end I would write $\sum_{k=1}^{n+1}(2k-1)=2n+1+\sum_{k=1}^n(2k-1)=2n+1+n^2=(n+1)^2$

herb steinberg
  • 12,765