1
$\begingroup$

Is there a way to show that $$(a+b)^n=\sum_{k=0}^n \binom{n}{k}a^kb^{n-k}$$ where $a,b$ are positif integer with out using induction ?

$\endgroup$
1
  • $\begingroup$ How do you want to define ${n \choose k}$? One popular way is as the coefficient of $a^k b^{n-k}$ in the expansion of $(a+b)^n$. $\endgroup$ Oct 8 '15 at 20:30
2
$\begingroup$

$$(a+b)^n=(a+b) \dots (a+b)$$ with $n$ terms. Use then combinatorics to find for $0 \le k \le n$ the number of ways to get a term $a^kb^{n-k}$.

$\endgroup$
1
  • $\begingroup$ It's quite good and efficient :-) (+1) $\endgroup$
    – Surb
    Oct 8 '15 at 20:46
0
$\begingroup$

Let $A,B$ sets such that $A\cap B=\emptyset$ and $|A|=a$ and $|B|=b$.$$(a+b)^n=\big|\{f:\{1,...,n\}\longrightarrow A\cup B\mid n\in\mathbb N\}\big|.$$

But you can count those functions differently ! Count the number of function $$f:\{1,...,n\}\longrightarrow A\cup B$$ that launch $k$ elements in $A$ and $n-k$ elements in $B$. Take $k$ elements of $\{1,...,n\}$ (with $\binom{n}{k}$ possibilities) and launch them to an element of $A$. Each element has $a$ possibilities. Then, take the other $n-k$ elements and launch them to an element of $B$. Each element has $b$ possibilities. Therefore, there is $$\binom{n}{k}a^{k}b^{n-k}$$ that through $k$ elements in $A$ and $n-k$ elements in $B$. Finally, you get $$\big|\{f:\{1,...,n\}\longrightarrow A\cup B\mid n\in\mathbb N\}\big|=\sum_{k=0}^n\binom{n}{k}a^kb^{n-k}.$$

$\endgroup$
0
$\begingroup$

Inspired by Wikipedia:

To get some intuition, expand this by distribution property:

(x+y)(x+y)(x+y)= (xx + xy + yx + yy)(x+y)

= xxx + xyx + yxx + yyx + xxy + xyy + yxy + yyy

It's like flipping a coin and counting all the possible outcomes after adding more flips into the mix and so forth.

Notice that I'm not writing exponents, this is to make the pattern more evident.

You'll notice that there are three ways to write strings of two x's and one y in this example.

Binomial coefficients $\binom{n}{k}$ are defined (and can be derived entirely without touching the binomial formula!) as the amount of ways to choose k objects out of a group of n, disregarding order.

The rest falls in place.

$\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.