2

I am quite familiar with the algorithm of mathematical induction but I can't rationalize the inductive step very well. Suppose I have the classical example: $$0 + 1 +2 + \ldots + n = \frac{n(n+1)}{2}$$ In the inductive step I have to show that this hold for $k+1$ so I don't understand why I don't find written: $$0 + 1 +2 + \ldots + (k+1) = \frac{(k+1)((k+1)+1)}{2}$$ instead of: $$0 + 1 +2 + \ldots + k + (k+1) = \frac{(k+1)((k+1)+1)}{2}$$

Why the $k$ in the left-hand side of the equation in not substitute with $k+1$ as in the right-hand side of the equation. How can I rationalize the inductive step of mathematical induction? Can any one prove me that the first equation is also right and show me how to deal with the proof?

G M
  • 317
  • both the statements you write are the same and are correct. – Guy Jun 07 '14 at 12:36
  • @Sabyasachi thanks I have edited the question... – G M Jun 07 '14 at 12:39
  • They are still the same ... both left hand-sides range over all nonnegative integers between $0$ and $k+1$. – user144248 Jun 07 '14 at 12:41
  • What I think the OP misunderstands is the following: why does, in the second equation, $k$ (the second-to-last term) not substitute with $k+1$, so that the LHS should read as $0+1+2+\cdots+(k+1)+(k+1)$, which is a really funny thing to ask :=) – user144248 Jun 07 '14 at 12:50
  • @GM, you can write (k+1) instead of k, but then you will have to prove that the expression is also true for (k+2) – Vikram Jun 07 '14 at 12:55

3 Answers3

1

Can anyone prove me that the first equation is also right and show me how to deal with the proof?

Apparently you don't understand that the first and second equations are exactly the same,

$$0+1+\cdots+5$$

and $$0+1+\cdots+4+5$$

are the same things.

G M
  • 317
Guy
  • 8,857
  • 1
  • 28
  • 57
1

i don't know what exactly you mean. but the desired claim is that for every $n\in\mathbb{N}$ such $n=k+1\in\mathbb{N}$, the equality holds .

Now, in Inductive step, you suppose the proposition is true for $k$ and then you must prove the proposition for $k+1$. It means you must prove that:

$$1+\cdots+(k+1)=\frac{(k+1)((k+1)+1)}{2}$$

It's now easy to check above equality as :

$$1+\cdots+k+(k+1)=\frac{k(k+1)}{2}+k+1$$

Fardad Pouran
  • 2,178
1

Using induction you have $1 + 2 + \cdots + k = \frac{k(k + 1)}{2}$. Butthen you can write $1 + 2 + \cdots + k + (k + 1) = \frac{k(k + 1)}{2} + (k + 1)$. Now $$\frac{k(k + 1)}{2} + (k + 1) = (k + 1)(\frac{k}{2} + 1) = (k + 1)\frac{k + 2}{2} = \frac{1}{2}(k + 1(k + 2).$$ This is what you need to show.

Jay
  • 3,822