Lucho_Nevara

asked on

# discrete mathematics

1. prove by mathematical induction that: 1+2^n<=3^n for all n>=1.

2. give an example or prove that there are none.

a) a simple graph with degrees 1,2,2,3.

b) a simple graph with degrees 2,3,4,4,4.

c) a simple graph with degrees 1,1,2,4.

2. give an example or prove that there are none.

a) a simple graph with degrees 1,2,2,3.

b) a simple graph with degrees 2,3,4,4,4.

c) a simple graph with degrees 1,1,2,4.

Generally, when you ask us to do your homework for you, we prefer you show what you've done, or ask a specific question as to what you don't understand. Posting the exact text of your homework is a good way to get a visit from the moderators = )

ASKER

for question 1, i went this far:

for n=1, 1+2^1<=3^1 is true

suppose 1+2^k<=3^k and let's show that 1+2^(k+1)<=3^(k+1) (this is where i'm stranded and can't move forward).

for question 2,

a) represent 4 nodes with the associations

b)there is no example because the sum of the degrees 2+3+4+4+4=17 is odd.

c)there is no example because the highest degree for a 4-node simple graph is 3.

now i'm awaiting your answers.

for n=1, 1+2^1<=3^1 is true

suppose 1+2^k<=3^k and let's show that 1+2^(k+1)<=3^(k+1) (this is where i'm stranded and can't move forward).

for question 2,

a) represent 4 nodes with the associations

b)there is no example because the sum of the degrees 2+3+4+4+4=17 is odd.

c)there is no example because the highest degree for a 4-node simple graph is 3.

now i'm awaiting your answers.

For question 1:

Suppose 1 + 2^k <= 3^k for an k >= 1

you may try multiplying both side with (1+2) and see what happens.

Suppose 1 + 2^k <= 3^k for an k >= 1

you may try multiplying both side with (1+2) and see what happens.

ASKER

it does not help me. suggest something different please.

ASKER CERTIFIED SOLUTION

membership

Create an account to see this answer

Signing up is free. No credit card required.

ASKER

Upon expanding, I would have:

1+2^k+2+2^(k+1) <= 3^(k+1)

=> 1+2^(k+1)+2+2^k <= 3^(k+1)

we know that 1+2^(k+1) <= 1+2^(k+1)+2+2^k, therefore we have: 1+2^(k+1) <= 3^(k+1).

this completes the mathematical induction. Am I right?

1+2^k+2+2^(k+1) <= 3^(k+1)

=> 1+2^(k+1)+2+2^k <= 3^(k+1)

we know that 1+2^(k+1) <= 1+2^(k+1)+2+2^k, therefore we have: 1+2^(k+1) <= 3^(k+1).

this completes the mathematical induction. Am I right?

Spot on, just need to complete with check of initial value (e.g. 2)

ASKER

Thank you so much for your help. Would you mind assisting me with question 2?