Question

If 2 <= k <= n - 2, show that
\[\left(\begin{matrix}n \\ k\end{matrix}\right) = \left(\begin{matrix}n - 2 \\ k -2\end{matrix}\right) + 2\cdot\left(\begin{matrix}n-2 \\ k-1\end{matrix}\right) + \left(\begin{matrix}n-2 \\ k\end{matrix}\right)\]
for n >= 4.

Answer 1

If 2 <= k <= n - 2, show that
\[\left(\begin{matrix}n \\ k\end{matrix}\right) = \left(\begin{matrix}n - 2 \\ k -2\end{matrix}\right) + 2\cdot\left(\begin{matrix}n-2 \\ k-1\end{matrix}\right) + \left(\begin{matrix}n-2 \\ k\end{matrix}\right)\]
for n >= 4.

With Pascal's theorem I got so far:
\[\left(\begin{matrix}n \\ k\end{matrix}\right) = \left(\begin{matrix}n - 2 \\ k -2\end{matrix}\right) +\left(\begin{matrix}n-2 \\ k-1\end{matrix}\right) + \left(\begin{matrix}n-2 \\ k-1\end{matrix}\right) + \left(\begin{matrix}n-2 \\ k\end{matrix}\right)\]
\[\left(\begin{matrix}n - 2 \\ k -2\end{matrix}\right) +\left(\begin{matrix}n-2 \\ k-1\end{matrix}\right) + \left(\begin{matrix}n-2 \\ k-1\end{matrix}\right) + \left(\begin{matrix}n-2 \\ k\end{matrix}\right)= \left(\begin{matrix}n - 1 \\ k-1\end{matrix}\right) + \left(\begin{matrix}n - 1 \\ k+ 1\end{matrix}\right)\]

Not sure what to do next.

Answer 2

When you create pascal's triangle you take the two above and add them together to get the one below it, in binomial coefficients this is represented as:

\[\binom{n}{k}+\binom{n}{k+1} = \binom{n+1}{k+1}\]

So then I start here and you can visualize this as being sorta two levels up on the triangle (which is why there's that condition for where it's valid)
\[\binom{n-2}{k-2} + 2 \binom{n-2}{k-1} + \binom{n-2}{k}\]
\[\left[\binom{n-2}{k-2} + \binom{n-2}{k-1} \right] + \left[ \binom{n-2}{k-1} + \binom{n-2}{k}\right]\]
\[\binom{n-1}{k-1} + \binom{n-1}{k}\]
\[\binom{n}{k}\]

I know I didn't say much, but basically I'm visualizing this:

The thing starts out at the red, then simplifies to blue then down to green... Haha play with pascal's triangle a bit I'm probably overcomplicating it by drawing this obscure picture.

Answer 3

LHS \(\left(\begin{matrix}n\\k\end{matrix}\right)=\dfrac{n!}{(n-k)!*k!}\)

Answer 4

RHS :
first term:
\[\left(\begin{matrix}n-2\\k-2\end{matrix}\right)=\dfrac{(n-2)!}{(n-k)!*(k-2)!}\\=\dfrac{(n-2)!}{(n-k)!*(k-2)!}*\dfrac{(n-1)n(k-1)k}{(n-1)n(k-1)k}\\=\dfrac{n!}{(n-k)!k!}*\color{red}{\dfrac{k(k-1)}{n(n-1)}}\]

Answer 5

Second term:
\[2\left(\begin{matrix}n-2\\k-1\end{matrix}\right)=2\dfrac{(n-2)!}{(n-k-1)!*(k-1)!}\\=2\dfrac{(n-2)!}{(n-k-1)!*(k-1)!}*\dfrac{(n-1)n(n-k)k}{(n-1)n(n-k)k}\\=\dfrac{n!}{(n-k)!k!}*\color{red}{2\dfrac{k(n-k)}{n(n-1)}}\]

Answer 6

The third one:
\[\left(\begin{matrix}n-2\\k\end{matrix}\right)=\dfrac{(n-2)!}{(n-k-2)!*k!}\\=\dfrac{(n-2)!}{(n-k-2)!*k!}*\dfrac{(n-1)n(n-k-1)(n-k)}{(n-1)n(n-k-1)(n-k)}\\=\dfrac{n!}{(n-k)!k!}*\color{red}{\dfrac{(n-k-1)(n-k)}{n(n-1)}}\]

Answer 7

Now, add them up and factor \(\dfrac{n!}{(n-k)!k!}\) out, you calculate the red part and it equals 1. Hence LHS = RHS