Help with Induction Proofs for Beginners

  • Thread starter gcarson1
  • Start date
  • Tags
    Induction
In summary: You have to multiply it out correctly, and then you will get the correct thing to subtract from the other one. But then you also have to explain why if 3 divides
  • #1
gcarson1
7
0
Hi all, been struggling with my course material regarding Induction. My prof is really not great at explaining this proof method. I don't know what the learning curve or expectations here are like but I'm really struggling with this conceptually.

Any assistance with these problems would be much appreciated:

1. Prove that 3 divides n^3+2n whenever n is a positive integer.
I know I can't use a summation progression so how do I solve this induction?
(n+1)^3+2(n+1) is the next step but I get lost when I try to factor out the (n+1)^3
This is as far as I can take this one.

2. Prove that 1x1! + 2x2! + ... + nxn! = (n+1)!-1
Let P(n) be 1x1!+…+nxn!=(n+1)!-1
Basis Step: 1 x 1! = (1+1)!+1
1 = 1
Therefore our basis step is true.
Inductive Step: We know that P(n) is true thus we must prove P(n+1)
1x1!+…+nxn!+((n+1)(n+1)!)=[ 1x1!+…+nxn! ] + ((n+1)(n+1)!)
1x1!+…+nxn!+((n+1)(n+1)!)= [(n+1)!-1]+((n+1)(n+1)!)
1x1!+…+nxn!+((n+1)(n+1)!)= ((n+1)(n+1)!)

I believe this one is solved however I'm not sure if I must take it further?
 
Last edited:
Physics news on Phys.org
  • #2
1. Why are you factoring out (n+1)^3? You can't.

The philosophy of induction is to relate one statement to previous ones.

So, given (n+1)^3 + 2(n+1) and n^3+2n, what have you tried to do with both?
 
  • #3
matt grime said:
1. Why are you factoring out (n+1)^3? You can't.

The philosophy of induction is to relate one statement to previous ones.

So, given (n+1)^3 + 2(n+1) and n^3+2n, what have you tried to do with both?

Tried to divide both by 3 in order to redue the formula to a positive integer. Yet I still don't understand how to write or show this?
 
  • #4
Divide both sides of what by 3?

Do the only possible thing that you can do. Expand (n+1)^3+2(n+1). Then think.
 
  • #5
Ok I think I got it, the expansion is a little messy but here goes :
Prove that 3|n^3+2n whenever n is a positive integer.
Basis Step: 1^3+2(1)/3 = 3/3 = 1 then we know that the first step in the formula is true.
Inductive Step: 3|(n+1)^3+2(n+1) If both terms are multiples of 3 then they are divisible by 3 so:
3|(n+1)^3+2(n+1)- (n^3+2n)

Expand
(n+1)^3
(n+1)^2(n+1)
(n^2+n+1)n+(n^2+n+1)1
n^3+n^2+n+n^2+n+1
n^3+2n^2+2n+1
Insert back into equation
n^3+2n^2+2n+1+2n+2
Subtract Original formula
n^3+2n^2+4n+3 - (n^3+2n)
2n^2+2n+3
(2n)(2n)+2n+3
4n+2n+3
6n+3

Since the values are multiples of 3 the formula is divisible by 3 thus 3|(n+1)^3+2(n+1) is true.

Right?
 
Last edited:
  • #6
You made a mistake, by the binominal formula: (K+1)^3 = K^3 +3K^2+3K+1. (It is always true that if the power is a prime, (a+b)^p = a^p+b^p +p(middle terms).

We start with Basis: let n=1, 1^3+2(1) = 3.

If true for K, (K+1)^3 +2(K+1) = [k^3+2K] +3K^2+3K+1 +2 . The first part is divisible by 3 by the induction hypothesis and the second is 3K^2+3K+3, all terms divisible.
 
Last edited:
  • #7
As robert says, you don't have the correct binomial expansion. Plus you also write something that implies you think 2n^2=(2n)(2n)=4n which is also not true in two different ways.
 
  • #8
I got a bad feeling whn you declared "My prof is really not great at explaining this proof method." Now I see I was right. Your problem is not induction-your prof seems to have taught you that well. Your problem is algebra:
(n+1)^3
(n+1)^2(n+1) yes
(n^2+n+1)n+(n^2+n+1)1
No, (n+1)^2= n^2+ 2n + 1, not n^2+ 1
so
n^3+n^2+n+n^2+n+1
should be n^3+ 2n^2+ n+ n^2+ 2n+1 and you get n^3+ 3n^2+ 3n+ 1.

But far, far worse!
2n^2+2n+3
(2n)(2n)+2n+3
4n+2n+3
A thousand lashes with a wet noodle! 2n^2 is NOT(2n)(2n), that would be 4n^2. But anyway, (2n)(2n) is NOT 4n! You took the square off the n and put it on the 2- that's not cricket.
 
Last edited by a moderator:

1. What is an induction proof?

An induction proof is a mathematical method used to prove a statement or theorem for all possible values of a variable. It involves showing that the statement is true for a base case, and then using a logical argument to show that if the statement is true for one value, it is also true for the next value.

2. How do I know when to use an induction proof?

Induction proofs are commonly used to prove statements about sequences, series, and subsets of integers. They are also useful for proving mathematical identities and inequalities. If you are trying to prove a statement that involves a variable that can take on an infinite number of values, an induction proof is likely the best approach.

3. What are the steps for an induction proof?

The steps for an induction proof are as follows:

  • Step 1: Prove the statement is true for the base case (usually the smallest possible value of the variable).
  • Step 2: Assume the statement is true for a specific value of the variable (this is called the induction hypothesis).
  • Step 3: Use the induction hypothesis to show that the statement is also true for the next value of the variable.
  • Step 4: Conclude that the statement is true for all possible values of the variable by using the principle of mathematical induction.

4. Can you provide an example of an induction proof?

Sure! Let's say we want to prove that the sum of the first n positive integers is equal to n(n+1)/2. We can use induction to prove this statement.

  • Base case: When n = 1, the sum of the first n positive integers is 1, and n(n+1)/2 = 1(1+1)/2 = 1. So the statement is true for n = 1.
  • Induction hypothesis: Assume the statement is true for some positive integer k. This means that the sum of the first k positive integers is equal to k(k+1)/2.
  • Inductive step: We want to show that the statement is also true for k+1. The sum of the first k+1 positive integers is (k+1) added to the sum of the first k positive integers. Using our induction hypothesis, we can rewrite this as (k+1) + k(k+1)/2 = (k+1)(k+2)/2, which is equal to the sum of the first k+1 positive integers. Therefore, the statement is true for k+1.
  • Conclusion: By the principle of mathematical induction, the statement is true for all positive integers n.

5. Are there any common mistakes to avoid when using induction proofs?

One common mistake is not checking the base case. It is important to make sure that the statement is true for the smallest possible value of the variable. Additionally, it is important to be careful with the logic used in the inductive step – just because the statement is true for one value does not necessarily mean it is true for the next value. Lastly, it is important to be clear and precise in your wording and reasoning throughout the proof.

Similar threads

Replies
3
Views
2K
  • Linear and Abstract Algebra
Replies
3
Views
2K
  • Linear and Abstract Algebra
Replies
2
Views
912
  • Linear and Abstract Algebra
Replies
5
Views
2K
Replies
4
Views
1K
  • Calculus and Beyond Homework Help
Replies
15
Views
1K
  • Linear and Abstract Algebra
Replies
2
Views
3K
Replies
13
Views
1K
  • Linear and Abstract Algebra
Replies
12
Views
1K
  • Topology and Analysis
Replies
6
Views
1K
Back
Top