You are Here: Home >< Maths

# Proof by induction - mistake? watch

1. We're attempting to prove by induction that n^2 <= 2^n.

The proof given is as follows:

Assume for some k that k^2 <= 2^k

(k + 1)^2 = k^2 + 2k + 1 <= 2^k + 2k + 1 by assumption

Therefore, we need to show that 2k + 1 <= 2^k

Where in the world did that last line follow from? The rest of the proof goes on to prove that line, which I can follow, but that line doesn't make sense to me.
2. If 2k+1 <= 2^k then 2^k + 2k+1 <= 2^k + 2^k = 2(2^k) = 2^(k+1)
3. I think they want to show that .
4. Ah ok, that seems like quite a big step to skip out, but thanks. I get it now.
5. (Original post by sonofdot)
If 2k+1 <= 2^k then 2^k + 2k+1 <= 2^k + 2^k = 2(2^k) = 2^(k+1)
this

TSR Support Team

We have a brilliant team of more than 60 Support Team members looking after discussions on The Student Room, helping to make it a fun, safe and useful place to hang out.

This forum is supported by:
Updated: October 13, 2009
Today on TSR

### Cambridge interviews

Find out who is getting invitations

### University open days

• University of Roehampton
Sat, 17 Nov '18
• Edge Hill University
Faculty of Health and Social Care Undergraduate
Sat, 17 Nov '18
• Bournemouth University
Sat, 17 Nov '18
Poll
Useful resources

### Maths Forum posting guidelines

Not sure where to post? Read the updated guidelines here

### How to use LaTex

Writing equations the easy way

### Study habits of A* students

Top tips from students who have already aced their exams