Proofs By Induction: Proving P(n) for All n

[ver_mathstats]

Homework Statement

Suppose we want to prove using mathematical induction that for all positive integers n, 1²+2²+...+n² = (n(n+1)(2n+1))/6. What do we need to prove in the inductive step of our proof?

Homework Equations

The Attempt at a Solution

I am struggling to understand what this means.

I put n is equal to 3.

So 1²+2²+3²=14

And (3(3+1)(2(3)+1))/6= 14

To hold that this formula holds for all n we use PMI.

First we have to figure out what P(n) we are trying to prove is true for all positive integers n.

I am confused what the P(n) statement is.

We want to apply PMI to conclude that P(n) is true for all positive integers n.

We need to show two things:

PMI 1 is true. That is P(1) is true.

PMI 2 is true. That is for any m ∈ ℤ, if P(m) is true then (m+1)(2m+1) is true.

If we can prove both of these, then PMI tells us that we can conclude that P(n) is true for all positive integers.

How is this so far?

I still am unsure how of how to answer the original question.

Thank you.

 

[fresh_42]

Homework Statement

Suppose we want to prove using mathematical induction that for all positive integers n, 1²+2²+...+n² = (n(n+1)(2n+1))/6. What do we need to prove in the inductive step of our proof?

Homework Equations

The Attempt at a Solution

I am struggling to understand what this means.

I put n is equal to 3.

So 1²+2²+3²=14

And (3(3+1)(2(3)+1))/6= 14

To hold that this formula holds for all n we use PMI.

First we have to figure out what P(n) we are trying to prove is true for all positive integers n.

The structure of an induction to prove a statement $S(n)$ is always as follows:
a) Prove $S(n_0)$ for a certain number $n_0$, here we have $S(n) \, : \,\sum_{k=1}^n k^2 = \dfrac{n(n+1)(2n+1)}{6}$ and thus $S(1)=1^2=\dfrac{1\cdot (1+1) \cdot (2\cdot 1 +1)}{6}=1$ which is true.

Now we can continue and check $S(2), S(3), S(4), S(5), \ldots$ but where ever we will stop, we will never have checked all numbers. So instead we make use of the fact that every natural number $n$ has an successor $n+1$. If you will, we just pretend that we have checked all statements $S(k)$ for $k=1,2,\ldots ,n$. However, this is just a mnemonic. What we do is, we take $S(n)$ for granted and conclude with it, that $S(n+1)$ is true as well. As $n$ can be any number, we have simulated the "and so on" from the starting point $n=n_0=1$.

Hence we know, that $\sum_{k=1}^n k^2 = \dfrac{n(n+1)(2n+1)}{6}$.
It now must be shown $S(n+1)$.

How can you prove $S(n+1)$ if $S(n)$ is given?

 

[haruspex]

What do we need to prove in the inductive step of our proof?

An inductive proof here would consist of
1. Finding some N for which it is true. You have done this with N=3, but you could have made it easier with N=1 or N=0.
2. Showing that IF it is true for n, where n≥N, THEN it is also true for n+1.

Note that in some problems where induction can be used, you may find that you need to choose a sufficiently large N in order for your inductive step to work. I don't see that being a problem here.

 

[Mark44]

I am confused what the P(n) statement is.

P(n) is the proposition or statement for which the index is n. In the case of this problem, P(n) is the statement that the sum of the squares of the first n positive integers is $\frac{n(n + 1)(2n + 1)} 6$. P(1) is the statement that the sum of the squares of the first 1 positive integers is $\frac {1(1 + 1)(2 \cdot 1 + 1)} 6$. Clearly, this is true.

There are three parts to an induction proof:
1. Show that the proposition is true for some starting value, say, P(1). This is called the base step. It doesn't necessarily have to be for n = 1.
2. Assume that P(k) is true; i.e., that the proposition is true for n = k. IOW, assume that the sum of the squares of the first k pos. integers is $\frac{k(k + 1)(2k + 1)}6$. This is called the induction hypothesis.
3. Show, using the induction hypothesis of step 2, that P(k + 1) is also true. IOW, show that the sum of the squares of the first k + 1 pos. integers is $\frac{(k + 1)(k + 2)(2(k + 1) + 1)} 6$. This is the induction step.