0

Is mathematical induction is about proving the expression or is it about proving that expression is valid over a set of value(natural number), assuming expression is correct?

qwerk
  • 21
  • See Mathematical induction : "Mathematical induction is a mathematical proof technique. It is essentially used to prove that a property $P$ holds for all natural numbers." If we work in a formalized setting, the property $P$ must be expressible with a formula of the language. – Mauro ALLEGRANZA May 10 '18 at 06:00
  • What do you mean by "proving that expression is valid ..., assuming expression is correct"? I can prove that the Moon is made of cheese for every natural number if I assume it is correct that the Moon is made of cheese, but that has nothing to do with mathematical induction. – David K May 10 '18 at 11:20
  • it your question is "what is mathematical induction about?", a short answer is "it is a way to prove that a statement $P$ is true on all natural numbers greater or equal to $k$ by showing that it is true for $k$ and that the fact that it is true for $n \ge k$ implies that it is also true for $n+1$. So you are assuming that a (somewhat) simpler case is true in order to show that next step is true. – mau May 10 '18 at 13:39
  • @David K what I meant, that we assume that given equation is correct and we do not need to care about the equation, we are only proving if that equation is correct for a natural number or not. – qwerk May 12 '18 at 04:41
  • I don't see how we can say an equation is "correct" if we find out that it is not correct for the natural number $3$ (for example). So I think induction is about proving the equation (which is an equation about natural numbers) is always true, that is, it is true for all natural numbers. But we prove it in the way described by the answers below. – David K May 12 '18 at 13:07

2 Answers2

0

Can you explain what you mean a little more? Induction can be described by a sort of domino effect. We prove that if we can knock over the first domino, and if one domino knocks over the succeeding domino, then we have knocked over all the dominoes. This can be used to prove a range of things that require the natural numbers. It can be something from a closed form expression of a recursive sequence, to facts about generators and relations of some algebra. Its use is very diverse.

0

Mathematical induction is a principle that can be used to prove a statement is true for all natural numbers (or all natural numbers past some initial starting point.)

The steps for induction are as follows. Prove that the statement is true for an initial value (usually $n=1$). This is known as the base case. Then we prove that if the statement is true for $n$ then it is true for $n+1$. This proves the statement for all $n$.

For instance, if you wanted to prove a statement like,

For all $n \in \mathbb{N}$ prove that $1+2+3+4 ... +n = \frac{n(n+1)}{2}$. We can verify that this is true for $n=1$ or $n=2$ or $n=3$, but how can we prove this is true for all possible $n$? This is where we can use induction.

We note that for $n=1$, $1 = \frac{1 \cdot (2)}{2}$ so the formula holds for $n = 1$.

Now suppose that for some $n \in \mathbb{N}$ that $1+2+3...+n = \frac{n(n+1)}{2}$. Then $1+2+3...+n + (n+1) = \frac{n(n+1)}{2}+ (n+1) = \frac{(n+1)(n+2)}{2}$. So the formula held for $n+1$! Thus by the principle of mathematical induction, the formula holds for all $n$.

I hope that helps!

user413766
  • 1,156
  • 7
  • 14