Question

Bored, here's a fun problem (or rather, seeing the different methods to prove it is fun), i'll upload a pic in a sec

Answer 1

I'm looking for a function based on n for an answer.

Answer 2

Try some values for n and see if you see a pattern...for example, if n = 3 we get:
\[\left(\begin{matrix}3 \\ 0\end{matrix}\right) +\left(\begin{matrix}3 \\ 1\end{matrix}\right)+\left(\begin{matrix}3 \\ 2\end{matrix}\right)+\left(\begin{matrix}3 \\ 3\end{matrix}\right) \]
Which is 1 + 3 + 3 + 1 = 8

Answer 3

2^n
If you consider it in terms of polynomials, (x+y)^n, you'll notice that there are 2^n different monomial terms, with coefficient one. A little pushing around will reveal that the coefficients of the combined terms are of the form \[\left(\begin{matrix}n \\ k\end{matrix}\right)\], so the problems are equivalent.

Answer 4

Correct! The problems are totally equivalent. One way to see it is to expand (x+y)^n using the binomial theorem:
\[(x+y)^{n} = \left(\begin{matrix}n \\ 0\end{matrix}\right)x^{n}+\left(\begin{matrix}n \\ 1\end{matrix}\right)x^{n-1}y+\cdots +\left(\begin{matrix}n \\ n-1\end{matrix}\right)xy^{n-1}+\left(\begin{matrix}n \\ n\end{matrix}\right)y^{n}\]
Then make a clever numerical substitution for x and y; x = 1, y = 1. This produces:
\[(1+1)^{n} = \left(\begin{matrix}n \\ 0\end{matrix}\right)(1)^{n}+\left(\begin{matrix}n \\ 1\end{matrix}\right)(1)^{n-1}(1)+\cdots +\left(\begin{matrix}n \\ n-1\end{matrix}\right)(1)(1)^{n-1}+\left(\begin{matrix}n \\ n\end{matrix}\right)(1)^{n}\]
\[2^{n} = \left(\begin{matrix}n \\ 0\end{matrix}\right)+\left(\begin{matrix}n \\ 1\end{matrix}\right)+\cdots +\left(\begin{matrix}n \\ n-1\end{matrix}\right)+\left(\begin{matrix}n \\ n\end{matrix}\right)\]