Mathenatucak Induction Problems in discrete math

In summary, mathematical induction is a proof technique used in discrete math to prove statements about natural numbers. It involves starting with the first natural number and showing that if a statement is true for one natural number, it is also true for the next natural number. This process is repeated until it can be shown that the statement is true for all natural numbers. Common types of mathematical induction problems in discrete math include proving divisibility or primality of numbers and proving the equality or inequality of mathematical expressions. The steps for solving a mathematical induction problem include proving the statement for the first natural number, assuming it is true for some natural number, showing it is true for the next natural number, and concluding that it is true for all natural numbers. Some tips for
  • #1
GoGoDancer12
14
0

Homework Statement



Prove that 3 divides n3 + 2n whenever n is a positive integer.

Homework Equations


The Attempt at a Solution



Basis Step :
P(1) : [13 + 2(1) ] /3
[1+2] /3
[3]/3
1
Since 3/3 =1, P(1) is true

Inductive Step:
[ k3 + 2k ] /3 = [(k +1)3 + 2(k+1) ] /3

[k(k2 + 2k)] /3 = [(k)3 + (3k)2 + 5k +3] /3

Homework Statement



Prove that f1 2 + f2 2 +...+ fn 2 when n is a positive integer.

Homework Equations


The Fibonacci numbers f0, f1, f2..., are defined by the equations f0 = 0, f1 = 1 and fn = fn-1 + fn-2 for n = 2,3,4...

The Attempt at a Solution



Basic Step:
P(1) : f1 2 = f1 * f2

12 = (1)*(1)
1= 1
Since f1 2 = f1 * f2 , P(1) is true.

Inductive Step:
fk 2 = fk * fk+1

fk 2 + fk+1 2
= f1+fk+1 + (fk+1)
 
Last edited:
Physics news on Phys.org
  • #2
For the first problem, I'm having some trouble understanding what you're doing.
You have established the base case, P(1). IOW, when n = 1, n^3 + 2n = 1 + 2 = 3, so the proposition is true for n = 1.

Assume that the proposition is true when n = k. IOW, assume that k^3 + 2k is divisible by 3. Another way to say this is that k^3 + 2k = 3m for some integer m.

Now, when n = k + 1, you want to show/prove that (k + 1)^3 + 2(k + 1) is divisible by 3. You do NOT want to show that k^3 + 2k = (k + 1)^3 + 2(k + 1), which is essentially what you wrote in your post.

To show that (k + 1)^3 + 2(k + 1) is divisible by 3, expand the two terms. You will need to use the assumption that k^3 + 2k = 3m.
 
  • #3
I'm lost about showing that (k + 1)^3 + 2(k + 1) is divisible by 3. I expanded the right side of the equation [k^3 + 2k)] /3 = [(k)^3 + (3k)^2 + 5k +3] /3. So, do I replace on the left side [k(k^2 + 2k)] /3 with 3m??
 
Last edited:
  • #4
GoGoDancer12 said:
I'm lost of showing that (k + 1)^3 + 2(k + 1) is divisible by 3. I expanded the right side of the equation [k^3 + 2k)] /3 = [(k)^3 + (3k)^2 + 5k +3] /3. So, do I replace on the left side [k(k^2 + 2k)] /3 with 3m??
This equation is bogus - [k^3 + 2k)] /3 = [(k)^3 + (3k)^2 + 5k +3] /3 - get rid of it, and also get rid of those /3 things that you have.

Take another look at what I said at the end of my previous post.
 
  • #5
Ok, what about the second problem??
 
  • #6
What is the second problem?
GoGoDancer12 said:
Prove that f1 2 + f2 2 +...+ fn 2 when n is a positive integer.
There's nothing there to prove. You have to have a statement of some kind in order to prove it.
 

1. What is mathematical induction?

Mathematical induction is a proof technique used to prove statements about natural numbers. It involves showing that a statement is true for the first natural number and then showing that if the statement is true for one natural number, it is also true for the next natural number. This process is repeated until it can be shown that the statement is true for all natural numbers.

2. How is mathematical induction used in discrete math?

Mathematical induction is used in discrete math to prove statements about sets of integers or natural numbers. This is because discrete math deals with finite, countable structures, which can be represented using natural numbers. By using mathematical induction, we can prove that a statement is true for all natural numbers in a set, which is an important concept in discrete math.

3. What are some common types of mathematical induction problems in discrete math?

Some common types of mathematical induction problems in discrete math include proving that a statement is true for all natural numbers, proving divisibility or primality of numbers, and proving the equality or inequality of mathematical expressions using induction.

4. What are the steps for solving a mathematical induction problem?

The steps for solving a mathematical induction problem are as follows:

  1. Prove the statement for the first natural number.
  2. Assume the statement is true for some natural number k.
  3. Show that the statement is true for the next natural number (k+1) using the assumption from step 2.
  4. Conclude that the statement is true for all natural numbers by the principle of mathematical induction.

5. What are some tips for successfully solving mathematical induction problems?

Some tips for successfully solving mathematical induction problems include:

  • Start by understanding the problem and the statement you are trying to prove.
  • Work through the base case and make sure it is true.
  • Use clear and concise notation to represent your steps.
  • Make sure to show all necessary steps and justify any assumptions.
  • Check your work and make sure your proof is correct and complete.

Similar threads

  • Calculus and Beyond Homework Help
Replies
6
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
983
  • Calculus and Beyond Homework Help
Replies
3
Views
1K
  • Calculus and Beyond Homework Help
Replies
5
Views
1K
  • Calculus and Beyond Homework Help
Replies
4
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
1K
  • Calculus and Beyond Homework Help
Replies
4
Views
848
  • Calculus and Beyond Homework Help
Replies
23
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
884
Replies
1
Views
1K
Back
Top