discrete mathematics

Lucho_Nevara
Lucho_Nevara used Ask the Experts™
on
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.
Comment
Watch Question

Do more with

Expert Office
EXPERT OFFICE® is a registered trademark of EXPERTS EXCHANGE®
kaufmedGlanced up at my screen and thought I had coded the Matrix...  Turns out, I just fell asleep on the keyboard.
Most Valuable Expert 2011
Top Expert 2015

Commented:
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  = )

Author

Commented:
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 KwanAnalyst Programmer

Commented:
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.

 
Fundamentals of JavaScript

Learn the fundamentals of the popular programming language JavaScript so that you can explore the realm of web development.

Author

Commented:
it does not help me. suggest something different please.
Analyst Programmer
Commented:
1+2^k <= 3^k
=> (1+2)(1+2^k) <= (1+2)(3^k)

The next step, for the left side, try expanding it using (a+b)(c+d) = ac+bc+ad+bd), then you will see.

Hint: The following rule is useful. If a <= b and b <= c implies a <= c.


Author

Commented:
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?

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

Author

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

Do more with

Expert Office
Submit tech questions to Ask the Experts™ at any time to receive solutions, advice, and new ideas from leading industry professionals.

Start 7-Day Free Trial