2
$\begingroup$

I have just started my first course in discrete math and have some reflections.

If I want to calculate the sum

${n \choose 0}+{n \choose 1}x+{n \choose 2}x^2+...+{n \choose n-1}x^{n-1}+{n \choose n}x^n$, (1)

where $n$ is a natural number, I can effectively use the binomial theorem to see that the sum equals $(x+1)^n$. I can also give a combinatorial explanation for it which indeed is one way to prove the aforementioned theorem.

Many basic "standard exercises" ask me to calculate sums on this form with different values of $x$ and in these cases I have just applied the binomial theorem and quickly got an satisfying answer. But after some reflections it now feels like I´m "attacking" the problems from behind, with the proviso that I knew the sum took the form of a binomial expansion. Maybe this is a tool in problem solving? As an example:

For $x=10$ in the sum (1). I would see that $x=10$ just got substituted into the binomial expansion of $(x+1)^n$ and so the answer would be $11^n$.

But is there any other "easy" way to see that the result of (1). is $(x+1)^n$ without starting out with just recognizing the form of the sum? Let´s say I didn´t recognize that it was the binomial expansion of $(x+1)^n$ at first, how would I convince myself that´s clearly the case? Is there maybe some nice combinatorial explanations to attack the problem from this way also?

I do understand that I´ve already might have solve the problem in a effective way, but my reflections worries me that I have missed something fundamental in the theory. I prefer to achieve a deeper understanding of concepts than just memorizing facts.

$\endgroup$
1
$\begingroup$

Convince yourself of the proof of the binomial theorem instead. That way it will not matter what "direction" you go, as you will understand fully why the binomial theorem works.

First, note that the binomial theorem holds true for $n=0$. That is, $$ \left(1+x\right)^{0}=1=\sum_{k=0}^{0}\binom{n}{k}x^{k}=\binom{0}{0}x^{0}=1. $$

Proceed by induction. Induction works by assuming that something works for a given $n$ and showing that it also works for $n+1$. Since we already know it holds for $0$, we can apply our proof to show that it holds for $1$, $2$, etc..

Suppose that the binomial theorem holds for a particular fixed $n$. That is, $$ \left(1+x\right)^{n}=\sum_{k=0}^{n}\binom{n}{k}x^{k}. $$ Then, \begin{align*} \left(1+x\right)^{n+1} & =\left(1+x\right)\left(1+x\right)^{n}\\ & =\left(1+x\right)\sum_{k=0}^{n}\binom{n}{k}x^{k}\\ & =\ldots?\text{ (think about this)} \end{align*} You will need to use the identity $$ \binom{n}{k}+\binom{n}{k-1}=\binom{n+1}{k}. $$ You can also prove the above identity by induction.

$\endgroup$
1
$\begingroup$

Expand $$ (1+x)^n = (1+x)(1+x)\times (1+x) $$ As there are $n$ factors that are either $1$ or $x$, this has the expanded form $$ \sum_{k=0}^n a_k x^k $$

$a_k$ is the number of times you get $k$ $x$s. As there are $n$ factors and that every product $$ b_1 b_2 \dots b_n $$ with $b_i\in\{1,x\}$ are present in the sum, the number of such products is $\binom nk$.

Conclusion: $$ (1+x)^n = \sum_{k=0}^n \binom nk x^k $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.