2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ both the statements you write are the same and are correct. $\endgroup$ – Guy Jun 7 '14 at 12:36
  • $\begingroup$ @Sabyasachi thanks I have edited the question... $\endgroup$ – G M Jun 7 '14 at 12:39
  • $\begingroup$ They are still the same ... both left hand-sides range over all nonnegative integers between $0$ and $k+1$. $\endgroup$ – user144248 Jun 7 '14 at 12:41
  • $\begingroup$ 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 :=) $\endgroup$ – user144248 Jun 7 '14 at 12:50
  • $\begingroup$ @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) $\endgroup$ – Vikram Jun 7 '14 at 12:55
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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$$

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

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.