# Prove by induction

1. Dec 9, 2011

### Firben

Prove by induction that n^2 + n ≤ 2^n

for all integers n≥5

How i did:

Case(1)

Suppose that n = 5

LHS = 5^2 +5 = 30

RHS = 2^5 = 32

30 ≤ 32

Ok LHS ≤ RHS

Case (2)

Suppose thats true for n=p≥5. Show that its true for n = p+1

What should i do next ? I had a memory loss here :(

2. Dec 9, 2011

### Fredrik

Staff Emeritus
Just write down $(p+1)^2+(p+1)$ and work with that expression until you see that it's $\leq 2^{p+1}$. You will have to use the assumption $p^2+p\leq 2^p$.

3. Dec 12, 2011

### Firben

LHS(p+1) = (p+1)^2 + p+1 = p^2 + 2p + 1 + p + 1 = p^2 +3p + 2

How can i continue ?

4. Dec 12, 2011

### Mentallic

Well, what's your assumption?

5. Dec 12, 2011

### Firben

Yes, i think so

6. Dec 12, 2011

### Fredrik

Staff Emeritus
No, he asked "what's your assumption?", and you were supposed to answer "that the formula I want to prove for all n≥5 holds when n=p".

Last edited: Dec 12, 2011