Avatar of Lucho_Nevara
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.
Math / Science

Avatar of undefined
Last Comment
Lucho_Nevara

8/22/2022 - Mon
kaufmed

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  = )
Lucho_Nevara

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.
Peter Kwan

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.

 
Experts Exchange is like having an extremely knowledgeable team sitting and waiting for your call. Couldn't do my job half as well as I do without it!
James Murphy
Lucho_Nevara

ASKER
it does not help me. suggest something different please.
ASKER CERTIFIED SOLUTION
Peter Kwan

Log in or sign up to see answer
Become an EE member today7-DAY FREE TRIAL
Members can start a 7-Day Free trial then enjoy unlimited access to the platform
Sign up - Free for 7 days
or
Learn why we charge membership fees
We get it - no one likes a content blocker. Take one extra minute and find out why we block content.
Not exactly the question you had in mind?
Sign up for an EE membership and get your own personalized solution. With an EE membership, you can ask unlimited troubleshooting, research, or opinion questions.
ask a question
Lucho_Nevara

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?
rabarlow

Spot on, just need to complete with check of initial value (e.g. 2)
Get an unlimited membership to EE for less than $4 a week.
Unlimited question asking, solutions, articles and more.
Lucho_Nevara

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