# Newton formula with out using induction

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 ?

• 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$. Oct 8 '15 at 20:30

$$(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}$.

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

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

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.