Discrete Structure20805 marksPigeonhole principle
What is the pigeonhole principle? Show that binomn+1k=binomnk−1+binomnk\\binom{n+1}{k} = \\binom{n}{k-1} + \\binom{n}{k}binomn+1k=binomnk−1+binomnk where nnn and kkk are positive integers with n≥kn \geq kn≥k .
What is the pigeonhole principle? Show that binomn+1k=binomnk−1+binomnk\binom{n+1}{k} = \binom{n}{k-1} + \binom{n}{k}binomn+1k=binomnk−1+binomnk where nnn and kkk are positive integers with n≥kn \geq kn≥k . [5]
--- Definition: If n + 1 or more objects (pigeons) are placed into n containers (pigeonholes), then at least one container must contain two or more objects. Formal Statement: If a function $f: A \to B$ where $A B$, then $f$ is not injective (not one-to-one), meaning at least two elements of $A$ m...