Question

Proof (n+1 choose k+1)=( n choose k)+(n choose k+1)

Answer 1

@ganeshie8

Answer 2

pascal's identity

Answer 3

\[^{n+1}C_{k+1} = \frac{(n+1)!}{(k+1)! \cdot (n + 1 - k - 1)!} \implies \frac{(n+1)!}{(k+1)! \cdot (n-k)!}\]

Answer 4

Okay, so by definition, n choose k equals
\[\left(\begin{matrix}n \\ k\end{matrix}\right) = \frac{ n! }{ k! (n-k)! }\]
So \[\left(\begin{matrix}n+1 \\ k+1\end{matrix}\right) = \frac{ (n + 1)! }{ (k + 1)! ((n + 1) - (k + 1))! }\ = \frac{ (n + 1)! }{ (k + 1)! ((n - k)! }\]
Also, \[\left(\begin{matrix}n \\ k\end{matrix}\right) + \left(\begin{matrix}n \\ k + 1\end{matrix}\right) = \frac{ n! }{ k! ((n - k)! }\ + \frac{ n! }{ (k + 1)! ((n - (k + 1))! }\] \[= \frac{ n! }{ k! ((n - k)! }\ + \frac{ n! }{ (k + 1)! (n - k - 1)! }\]
Let's multiply the top and bottom of each term in the above equation by the necessary term to get a single denominator. Remember that \[n! = n * (n-1) * (n-2) * ... * 1\]
\[\frac{ n! (k+1)}{ k! ((n - k)!(k+1) }\ + \frac{ n!(n-k) }{ (k + 1)! (n - k - 1)!(n-k) }\]
\[=\frac{ n! (k+1)}{ (k+1)! ((n - k)! }\ + \frac{ n!(n-k) }{ (k + 1)! (n - k)! }\]
\[=\frac{ n! (n + k - k+1)}{ (k+1)! ((n - k)! }\]
\[ =\frac{ n! (n+1)}{ (k+1)! ((n - k)! }\]
\[ =\frac{ (n+1)!}{ (k+1)! ((n - k)! }\]
\[ = \left(\begin{matrix}n+1 \\ k+1\end{matrix}\right)\]

Answer 5

@Blacksteel you multiplied the top and bottom of each term by (k+1)!(n-k)!

Answer 6

Actually I multiplied the top and bottom of the first term by k + 1 and the top and bottom of the second by (n-k), then simplified.

Answer 7

Just open up the things..

Answer 8

\[(k+1)! = (k+1) \cdot k!\]

Answer 9

\[(n-k)! = (n-k) \cdot (n-k-1)!\]

Answer 10

Now look at colored things..

Answer 11

This is where you are now:
\[= \frac{ n! }{ k! \cdot \color{green}{((n - k)!} }\ + \frac{ n! }{ \color{green}{(k + 1)!} \cdot (n - k - 1)! }\]

Answer 12

Change them according to those two equations I have written above..

Answer 13

Thank you so much @waterineyes and @Blacksteel :)

Answer 14

\[= \frac{ n! }{ k! \cdot \color{green}{((n - k) \cdot (n-k-1)!} }\ + \frac{ n! }{ \color{green}{(k + 1) \cdot k!} \cdot (n - k - 1)! }\]

Answer 15

Is it clear now?

Answer 16

Yes

Answer 17

Now you are to just make out common denominator and proceed.. :)
Good. :)

Answer 18

I agree with @ganeshie8 , this is known is Pascal Identity. Read about it on
http://en.wikipedia.org/wiki/Pascal%27s_rule
This link has several proofs of it