discrete mathematics

Lucho_Nevara used Ask the Experts™
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.
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

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


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

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.


it does not help me. suggest something different please.
Analyst Programmer
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.


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?

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


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