LFD Book Forum - Problem 2.5

LFD Book Forum (http://book.caltech.edu/bookforum/index.php)

- Chapter 2 - Training versus Testing (http://book.caltech.edu/bookforum/forumdisplay.php?f=109)

- - Problem 2.5 (http://book.caltech.edu/bookforum/showthread.php?t=4704)

CountVonCount

10-25-2016 01:46 AM

Problem 2.5

Hello,

I tried to prove the unequally of problem 2.5 on page 69:

https://latex.codecogs.com/gif.latex...+&space;1

However I was not able to find a good prove. I tried by using the same scheme like in the prove for

https://latex.codecogs.com/gif.latex...ce;=&space;2^N

But I had no success.

Can anyone give me the answer or at least a hint, how to start the prove well?

Thanks a lot,
André

P.S.: Is there a good way to embedd latex to this Forum? At the moment I just use https://www.codecogs.com for generating latex pictures.

P.P.S.: The book is very good and the course videos make a lot of fun to watch. Really: Thanks to everyone who worked on it!

ntvy95

11-14-2016 08:18 PM

Re: Problem 2.5

I hope that I didn't make any mistake.

Base cases:

: $\sum_{i=0}^{0}\binom{N}{i} \leq N^{0} + 1 \Leftrightarrow 1 \leq 2$

: $\sum_{i=0}^{1}\binom{N}{i} \leq N^{1} + 1 \Leftrightarrow N + 1 \leq N + 1$

: $\sum_{i=0}^{2}\binom{N}{i} \leq N^{2} + 1 \Leftrightarrow \frac{N^{2}}{2} + \frac{N}{2} + 1 \leq \frac{N^{2}}{2} + \frac{N^{2}}{2} + 1 \leq N^{2} + 1$

Induction step for

$\sum_{i=0}^{D}\binom{N}{i} = \sum_{i=0}^{D-1}\binom{N}{i} + \binom{N}{D} \leq N^{D-1} + 1 + \binom{N}{D}$

I will prove $\frac {N!}{(N-D)!} \leq N^{D}$ later, for now, I will use its result:

$N^{D-1} + 1 +\binom{N}{D} \leq N^{D-1} + 1 + \frac {N^{D}}{D!}$

$D > 2 \Rightarrow D! > 2 \Leftrightarrow \frac{1}{D!} < \frac{1}{2}$ :

$N^{D-1} + 1 + \frac {N^{D}}{D!} \leq N^{D-1} + 1 + \frac {N^{D}}{2}$

$D > 2, N \geq D \Rightarrow N > 2 \Leftrightarrow \frac {1}{N} < \frac {1}{2} \Leftrightarrow \frac {N^{D-1}}{N^{D}} < \frac {1}{2} \Leftrightarrow N^{D-1} < \frac {N^{D}}{2}$ :

$N^{D-1} + 1 + \frac {N^{D}}{2} \leq \frac {N^{D}}{2} + 1 + \frac {N^{D}}{2} \leq N^{D} + 1$

So $\sum_{i=0}^{D}\binom{N}{i} \leq N^{D} + 1$ follows.

Quote:

Prove:

$\frac {N!}{(N-D)!} \leq N^{D}$

$\frac{1}{N^{D}} \times \frac {N!}{(N-D)!} = \frac{1}{N^{D}} \times \prod_{i=0}^{D+1} (N - i) = \prod_{i=0}^{D+1} \frac{N - i}{N^{D}} \leq 1$

k_sze

03-16-2018 09:07 AM

Re: Problem 2.5

Quote:

Originally Posted by ntvy95 (Post 12511)

$\frac{1}{N^{D}} \times \frac {N!}{(N-D)!} = \frac{1}{N^{D}} \times \prod_{i=0}^{D+1} (N - i) = \prod_{i=0}^{D+1} \frac{N - i}{N^{D}} \leq 1$

Aside from the slight mistake in the product (it should be $\prod_{i=0}^{D-1} (N - i)$ ), the whole proof is just amazing! How did you even come up this chain of logic and deduction?

All times are GMT -7. The time now is 03:56 PM.

Powered by vBulletin® Version 3.8.3
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.
The contents of this forum are to be used ONLY by readers of the Learning From Data book by Yaser S. Abu-Mostafa, Malik Magdon-Ismail, and Hsuan-Tien Lin, and participants in the Learning From Data MOOC by Yaser S. Abu-Mostafa. No part of these contents is to be communicated or made accessible to ANY other person or entity.