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

In summary: In the base step, we just assume that the proposition is true for some number, say, n = 3. In the induction hypothesis, we assume that the sum of the squares of the first k pos. integers is ##\frac{k(k + 1)(2k + 1)} 6##. This is because we're looking for a value of k such that the sum of the squares of the first k + 1 pos. integers is also ##\frac{k(k + 1)(2k + 1) + 1}{6}##. So, n = 3 is a good candidate. In the induction step, we use the induction hypothesis to show that P(k + 1) is also true.
  • #1
ver_mathstats
260
21

Homework Statement


Suppose we want to prove using mathematical induction that for all positive integers n, 12+22+...+n2 = (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 12+22+32=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.
 
Last edited:
Physics news on Phys.org
  • #2
ver_mathstats said:

Homework Statement


Suppose we want to prove using mathematical induction that for all positive integers n, 12+22+...+n2 = (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 12+22+32=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?
 
  • #3
ver_mathstats said:
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.
 
  • #4
ver_mathstats said:
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.
 

1. What is a proof by induction?

A proof by induction is a mathematical technique used to prove that a statement or formula is true for all values of a variable. It involves breaking down the statement into smaller cases and proving that it holds for each individual case, which then leads to the conclusion that it holds for all cases.

2. How does a proof by induction work?

A proof by induction works by first proving that the statement is true for a base case, typically when the variable is equal to 0 or 1. Then, assuming that the statement is true for a particular value of the variable, the proof shows that it must also be true for the next value of the variable. This process is repeated until it is shown that the statement is true for all values of the variable.

3. What is the role of the inductive hypothesis in a proof by induction?

The inductive hypothesis is the assumption that the statement is true for a particular value of the variable. This assumption is used to prove that the statement is true for the next value of the variable, and is essential in the process of proving the statement for all values of the variable.

4. Can a proof by induction be used for all mathematical statements?

No, a proof by induction can only be used for statements that have a clear structure and can be broken down into smaller cases. It cannot be used for statements that involve infinite sets or cases that cannot be easily divided into smaller cases.

5. Are there any limitations to using a proof by induction?

Yes, there are limitations to using a proof by induction. It can only be used for statements that are true for all values of the variable, and it cannot be used to prove the uniqueness of a solution. Additionally, it requires a solid understanding of mathematical logic and may not be suitable for complex or abstract problems.

Similar threads

  • Calculus and Beyond Homework Help
Replies
6
Views
852
  • Calculus and Beyond Homework Help
Replies
7
Views
302
  • Calculus and Beyond Homework Help
Replies
20
Views
1K
  • Calculus and Beyond Homework Help
Replies
5
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
522
  • Calculus and Beyond Homework Help
Replies
1
Views
434
  • Calculus and Beyond Homework Help
Replies
13
Views
2K
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
24
Views
617
  • Calculus and Beyond Homework Help
Replies
6
Views
965
Back
Top