• Support PF! Buy your school textbooks, materials and every day products Here!

Mathenatucak Induction Problems in discrete math

  • #1

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:

Answers and Replies

  • #2
33,516
5,196
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
33,516
5,196
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
33,516
5,196
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.
 

Related Threads on Mathenatucak Induction Problems in discrete math

Replies
7
Views
4K
  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
1
Views
813
  • Last Post
Replies
9
Views
2K
Replies
1
Views
850
Replies
13
Views
2K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
2
Views
655
  • Last Post
Replies
4
Views
911
Top