Binomial expansion

It's best if you try to answer this question without looking it up.

The binomial expansion uses the combinatorial function for it's coefficient.

What does combinations have to do with coefficients of an expansion?

One easy way to think of it is as follows:-
Consider (a+b)(c+d); this = ac+bc+ad+bd (2^2 entries): i.e. combine one from (a or b) with one from (c or d).
Continue (a+b)(c+d)(e+f) = ace+acf+....bdf : (2^3 entries) again all combinations using one from each of {a,b} {c,d} {e,f}

Thus if it was (x+y)(x+y)...(x+y) then the result would start xx...xx xx...xy and end yy...yy , with 2^N individual entries.
Unlike {a,b}{c,d}{e,f}, there was {x,y}{x,y}...{x,y}{x,y}, so we can combine all similar entries...
There's only one entry with all x's [i.e. where you pick the first of all {x,y}] - so 1 * x^N.
There's N ways to get one y and (N-1) x's - so N * x^(N-1) * y
etc.
Similarly starting with all y's gets the second part.

Another way to think about it is using induction.
X + Y
(X+Y)(X+Y) = X(X+Y) + Y(X+Y) = XX+2XY+YY
Above(X+Y) = X(XX+2XY+YY)+Y(XX+2XY+YY) = XXX+X2XY+YXX+XYY+Y2XY+YYY = XXX + 3XXY + 3XYY + YYY
and noticing that XXX..XXX can only come from X * XX..XXX whereas XXX..YYY can come from X * XX..YYY and Y * XXX..YY etc. which is the same as how 1 11 121 1331 14641.... is built up.

Quote: pacomartin

What does combinations have to do with coefficients of an expansion?

You have (x + y)^2 = x^2 + 2 xy + y^2.

The coefficient 2 in the xy term comes from xy + yx when you multiply (x+y)*(x+y). Each summand is a different combination how you can arrange one x and one y. The 2 is the actual number of those combinations.

In the (x+y)^n expansion there are c terms all like x^k y^(n-k), where c is the number of combinations how you can arrange k times x and (n-k) times y.

Nothing mystical, merely a beautiful side of math.

Quote: MangoJ

Nothing mystical, merely a beautiful side of math.

I always liked those things in mathematics. How what appears to be two different problems is just the same problem with a different wrinkle.

Like the connection between the definitions of tangent, cotangent, secant and cosecant in trigonometry and geometry.

deleted

Quote: Ibeatyouraces

My favorite equation:

$$ + $$ = more $$$$$$$... :-)

If you see this, could you please turn on your PM's for just a second?

Quote: pacomartin

How what appears to be two different problems is just the same problem with a different wrinkle.

Most often these connections give rise to a more deeper understanding.

In the same way you find (x+y)^n = sum_k C(n,k) x^k y^(n-k) you could define more generalized binomial coefficients C(n,k1,k2,...) as

(x1 + x2 + x3 + ...)^n = sum_(k1,k2,k3,k4) C(n,k1,k2,k3,...) x1^k1 x2^k2 x3^k3

Quote: MangoJ

Nothing mystical, merely a beautiful side of math.

So here is another unexpected pattern that I stumbled across back in my high school days. I don't know whether there is any significance that has escaped me, but I always thought it was intriguing.

Write the single-digit natural numbers in a row, like:

1 2 3 4 5 6 7 8 9

For the second row, square these numbers but only keep the last digit, like:

1 4 9 6 5 6 9 4 1

There's just a simple symmetry to that row, but now try cubing the numbers and keeping just the last digit:

1 8 7 4 5 6 3 2 9

That's the same list of natural numbers, each appearing exactly once, just in a scattered sequence. (Anything special about the sequence?) Next try this to the 4th power:

1 6 1 6 5 6 1 6 1

Again, symmetry and a pattern that surprised me when I first saw it. The real surprise (to me anyway) was when I tried the 5th power:

1 2 3 4 5 6 7 8 9

Now is that something that any of you would have expected? I certainly didn't. But as I have said, I was never a math major, just a bit of a high school nerd. And, of course, these patterns of final digits then repeat infinitely for higher powers.

That's pretty cool, Doc! I had never looked at that.

Quote: Doc

Write the single-digit natural numbers in a row, like:

1 2 3 4 5 6 7 8 9

Usually math is not that interesting if it relies on the numerical representation of numbers itself. It's like discussing a movie plot, where the characters are confused or mixed up with their corresponding actors.

The observed symmetry is always present in the beginning: you have numbers k to 10-k.
From that you could figure out that happens to the last digits of k^n and (10-k)^n.

Quote: Doc

Write the single-digit natural numbers in a row, like:

1 2 3 4 5 6 7 8 9

(...)
Next try this to the 4th power:

1 6 1 6 5 6 1 6 1

Again, symmetry and a pattern that surprised me when I first saw it. The real surprise (to me anyway) was when I tried the 5th power:

1 2 3 4 5 6 7 8 9

Now is that something that any of you would have expected?

This is due to Fermat's little theorem: For any prime p, x^(p-1) mod p = 1 for all x<p.

Your example (4th power) is for p=5. Thenthe fifth power takes into account the parity to produce the result for (mod 10).

Guess I didn't follow that. Maybe I got confused by the combination of the theorem including "mod p", your saying my example being "p=5", and "result for (mod 10)".

Please explain (for us slow folks): how does your comment (and that theorem) tell me to expect that any integer with a final digit of y, when raised to the 5th, 9th, 13th, 17th, etc. power, will also have a final digit of y?

(mod p) means the residue after division by p.

The "last digit", in the decimal system, is actually the residue mod 10.
Now a "residue mod 5 equal to 1" means a "last digit equal to 1 (if odd) or 6 (if even)". This happens for x^4, says Fermat, for any x (mod 5) = 1,2,3,4 , i.e. when the last digit of x(mod 10) = 1,2,3,4 or 6,7,8,9.

To reach x^5, multiply by x. For odd x, you have 1x = x . For even x, you have 6x= 5x + x= 10y + x. Last digit is x.

And of course, any 0^k ends in 0 and any 5^k ends in 5.

Example for p=3.

x = 1 2 3 4 5 6 7 8 etc (mod 3) = 1 2 0 1 2 0 1 2 etc
x² = 1 4 9 16 25 36 49 64 etc (mod 3) = 1 1 0 1 1 0 1 1 etc
x³ = 1 8 27 64 125 216 343 512 etc (mod 3) = 1 2 0 1 2 0 1 2 etc

Of course, p=5 is more impressive because of the decimal system.And because 10 is the product of two primes (for example, it doesn't work with 100).

Quote: kubikulann

This is due to Fermat's little theorem: For any prime p, x^(p-1) mod p = 1 for all x<p.

Your example (4th power) is for p=5. Thenthe fifth power takes into account the parity to produce the result for (mod 10).

You got to love math. Hey, isn't this cool! Yea, it is a trivial case of a theorem proved century ago.

Now prove that every even integer greater than 2 can be expressed as the sum of two primes.