You are Here: Home >< Maths

# Pigeonhole principle watch

I can't understand this proof.

I understand the f(i)<k+1 bit. But then I'm not really that convinced about explanation thats its injection. It just seems to say the obvious that if but still yeah I understand how the restricted function is injection by the inductive hypothesis. So that bits alright.

But its f(i)=k+1 for some i in N_m that is giving me trouble. I don't understand what the function g is doing.

Anyone?

Its page 133 or chapter 11 if it doesn't go to the section.

P.S. The lemma is so obvious too.
2. G is pimping out dem hos.

3. I don't know about anyone else, but google books is telling me that pages 125-153 aren't part of the preview, so we can't see the proof.
4. Click on 11 Properties of a finite sets

Its the first lemma proof. Not the actual Pigeonhole principle. I just don't understand the lemma that is used in the proof of the contraposition of Pigeonhole principle.

This lemma
If there exists an injection then

### Related university courses

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: July 15, 2009
Today on TSR

### Edexcel C3 Maths Unofficial Markscheme

Find out how you've done here

### 3,481

students online now

Exam discussions

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