3
$\begingroup$

Note: I am asking this question as a simple introductory question to proofs by induction, to which I will give also my formal answer (which should be correct, if not, please comment) for future visitors of this website.

I know that to prove something by induction, we need formally 3 steps (2, if we considere inductive hypothesis and inductive step together):

  1. Base case or basis:

    We determine what is the base case for our statement $P(n)$, and we immediately prove it.

  2. Inductive hypothesis:

    We assume our statement $P(n)$ is true for $n$.

  3. Inductive step:

    We try to prove that our statement is also true for $P(n + 1)$. If we can prove that, we can also prove that our statement is true for $n + 2$ (we don't need to do it), and so on.

    This step is usually the most difficult part, because it involves some algebraic manipulation, or some imagination in some way. For this last reason, it might be helpful watching other similar proofs by induction to solve the current one.

For example, suppose our $P(n)$ is the following:

$$\frac{n(n + 1)(2n + 1)}{6} = 0^2 + 1^2 + 2^2 + 3^2 + ... + n^2$$

which is basically saying that the sum of all squares of the natural numbers from $0$ to $n$ can be determined by the formula on the left side of the equation.

How would we prove $P(n)$ is true for all $n \in \mathbb{N}$?

For more information about the proof by induction, see the Wikipedia page about induction called Mathematical induction.

$\endgroup$

marked as duplicate by Jack D'Aurizio, Namaste, Zubin Mukerjee, MJD, user147263 Jan 11 '15 at 16:54

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

0
$\begingroup$

Like any proof by induction, we need to go through all 3 steps cited above for our example:

  1. Basis:

    Considering the first natural number is $1$, then our base case is $n = 1$, because we want to prove $P(n)$ for all natural numbers (It would also not make much sense to make the sum of $0$ members of the sequence).

    What we need to do is simply replacing $n$ with $1$s in our of formula, and check if the result is equals to the sum of the squares of the numbers until $1$ ($0^2 + 1^2 = 1$). So we have:

    $$\frac{1(1 + 1)(2 \cdot 1 + 1)}{6} = 0^2 + 1^2 = 1$$

    simplifying the left side expression, we have:

    $$\frac{(2)(3)}{6} = 0^2 + 1^2 = 1$$

    which is clearly a true statement.

  2. Inductive hypothesis:

    Here, we assume $P(n)$ is true for $n$, so we assume that $$\frac{n(n + 1)(2n + 1)}{6} = 0^2 + 1^2 + 2^2 + 3^2 + ... + n^2$$ is true.

  3. Inductive step:

    Now, we have to prove $P(n + 1)$ is also true. One usually technique is replacing $n$ with $n + 1$ in our statements, so we have:

$$\frac{(n + 1)((n + 1) + 1)(2(n + 1) + 1)}{6} = 0^2 + 1^2 + 2^2 + 3^2 + ... + n^2 + (n + 1)^2$$

Note that I have also added a new term for the right sequence $n + 1$, since our formula determines now the sum of all squares from $0$ to $n + 1$.

Now, you might think, how can we solve this? At this point, it might be useful to use something that you assumed, for example $P(n)$ for our example. In fact, you know that $$\frac{n(n + 1)(2n + 1)}{6} = 0^2 + 1^2 + 2^2 + 3^2 + ... + n^2$$

Can we see something that could be replaced in our $P(n + 1)$ with something from our $P(n)$? Yes, we could replace the sequence: $$0^2 + 1^2 + 2^2 + 3^2 + ... + n^2$$ with the corresponding formula: $$\frac{(n + 1)((n + 1) + 1)(2(n + 1) + 1)}{6} = \frac{n(n + 1)(2n + 1)}{6} + (n + 1)^2$$

If you solve the above statement, you will arrive at a true statement, something like $1 = 1$, which confirms that our statement is also true for $n + 1$, and that confirms, by induction, that $P(n)$ is valid for all $n \in \mathbb{N}$.

$\endgroup$
  • $\begingroup$ Toward the end, you say essentially that you want to prove $A=B$, and refer to manipulating until you get something true like $1=1$. This is a style of writing that (regrettably) is sometimes encouraged in high school, but that is in principle wrong. It is correct only if each step that led from $A=B$ to $1=1$ is reversible. I would strongly encourage proving that $A=B$ in this case by a direct calculation. $\endgroup$ – André Nicolas Jan 11 '15 at 18:23
  • $\begingroup$ @AndréNicolas Unfortunately, I am already too old to be at the high school, but thanks for the critic, I will try to see more examples later about this proof to see how can I improve it. Sincerely, I did not understand the last sentence of your statement (maybe because I am tired). What exactly do you mean by proving that A=B in this case by a direct calculation? $\endgroup$ – nbro Jan 11 '15 at 19:14
  • $\begingroup$ Bring the right-hand side ("$B$") to the common denominator $6$, then manipulate a bit. As a start, take out the common factor $n+1$ from the new numerator. Fairly quickly you will find that the right-hand side is equal to the left-hand side $\frac{(n+1)(n+2)(2n+3)}{6}$. $\endgroup$ – André Nicolas Jan 11 '15 at 19:19

Not the answer you're looking for? Browse other questions tagged or ask your own question.