Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I know you can easily expand $(x+y)^n$ using the binomial expansion. However, is there a simple summation formula for the following expansion?

$$(a_0+a_1x+a_2x^2+...+a_nx^n)^2$$

I found something called the multinomial theorem on wikipedia but I'm not sure if that applies to this specific problem. Thanks.

share|improve this question
6  
Yes, it applies. –  1015 Apr 11 '13 at 18:22

3 Answers 3

up vote 3 down vote accepted

The multinomial formula certainly applies. But for squares it is simpler: $$ (u_0 + u_1 + u_2 + \ldots + u_n)^2 = (u_0^2 + u_1^2 + \ldots u_n^2) + 2 (u_0 u_1 + u_0 u_2 + \ldots u_0 u_n + u_1 u_2 + \ldots u_1 u_n + \ldots + u_{n - 1} u_n) $$ Or just: $$ (u_0 + \ldots + u_n)^2 = \sum_{\substack{0 \le i \le n \\ 0 \le j \le n}} u_i u_j $$ But you are presumably interested in: $$ \left(\sum_{0 \le k \le n} a_k x^k\right)^2 = \sum_{\substack{0 \le i \le n \\ 0 \le j \le n}} a_i a_j x^{i + j} = \sum_{0 \le r \le 2 n} x^r \sum_{0 \le s \le r} a_s a_{r - s} $$ (in this formula assume $a_{n + 1} = \ldots = a_{2 n} = 0$)

share|improve this answer
    
What does the i,j notation in a summation mean? Thanks. –  Denise T Apr 11 '13 at 18:47
    
Sum over all $i, j$ pairs. Would probably render as $\sum_i \sum_j \ldots$ or such. –  vonbrand Apr 11 '13 at 18:49

To elaborate on the answer vonbrand gave, perhaps the following will help:

$$(a + b)^2 \;\; = \;\; a^2 + b^2 + 2ab$$

$$(a + b + c)^2 \;\; = \;\; a^2 + b^2 + c^2 + 2ab + 2ac + 2bc$$

$$(a + b + c + d)^2 \;\; = \;\; a^2 + b^2 + c^2 + d^2 + 2ab + 2ac + 2ad + 2bc + 2bd + 2cd$$

In words, the square of a polynomial is the sum of the squares of all the terms plus the sum of double the products of all pairs of different terms.

(added a few minutes later) I just realized Denise T wrote "... is there a simple summation formula for the following expansion", but maybe what I said could still be of help to others. What lead me to initially respond was her comment (which initially I misunderstood) "What does the i,j notation in a summation mean?", which suggested to me that perhaps she didn't understand sigma notation and thus vonbrand's answer was much too advanced.

(added 3 days later) Because of Denise T's comment, where she said in part "I am only familiar with basic sigma notation", and because of Wikipedia's notational-heavy treatment of the Multinomial theorem that in my opinion isn't very useful to someone who doesn't already mostly know the topic, I thought it would be useful to include a development that focuses more on the underlying ideas and technique. I would have written this earlier, but I've been extremely busy the past few days.

Notation: In what follows, ellipses (i.e. $\dots$) denote the continuation of a finite sum, not the continuation of an infinite sum.

Recall the (extended) distributive law: $$A(x+y+z+\dots) \; = \; Ax + Ay + Az + \dots$$ Using $A = (a+b+c+\dots)$, we get $$(a+b+c+\dots)(x+y+z+\dots)$$ $$= \; (a+b+c+\dots)x \; + \; (a+b+c+\dots)y \; + \; (a+b+c+\dots)z \; + \; \dots$$ Now imagine expanding each of the terms on the right side. For example, one such term to imagine expanding is $(a+b+c+\dots)y.$ It should be clear from this that the expansion of $(a+b+c+\dots)(x+y+z+\dots)$ consists of all possible products of the form

           (term from left sum) times (term from right sum)

The above can be considered a left brain approach. A corresponding right brain approach would be the well known school method of dividing a rectangle with dimensions $(a+b+c+\dots)$ by $(x+y+z+\dots)$ into lots of tiny rectangles whose dimensions are $a$ by $x$, $a$ by $y,$ etc. For example, see this diagram. Of course, the rectangle approach assumes $a,$ $b,$ $\dots,$ $x,$ $y,$ $\dots$ are all positive.

Now let's consider the case where the two multinomials, $(a+b+c+\dots)$ and $(x+y+z+\dots),$ are equal. $$(a+b+c+\dots)(a+b+c+\dots)$$ $$= \; (a+b+c+\dots)a \; + \; (a+b+c+\dots)b \; + \; (a+b+c+\dots)c \; + \; \dots$$ After expanding each of the terms on the right side, such as the term $(a+b+c+\dots)b,$ we find that the individual products of the form

           (term from left sum) times (term from right sum)

can be classifed into the these two types:

Type 1 product: $\;\;$ term from left sum $\;\; = \;\;$ term from right sum

Type 2 product: $\;\;$ term from left sum $\;\; \neq \;\;$ term from right sum

Examples of Type 1 products are $aa,$ $bb,$ $cc,$ etc. Examples of Type 2 products are $ab,$ $ba,$ $ac,$ $ca,$ $bc,$ $cb,$ etc.

When all the Type 1 products are assembled together, we get $$a^2 + b^2 + c^2 + \dots$$ When all the Type 2 products are assembled together, we get $$(ab + ba) \; + \; (ac + ca) \; + \; (bc + cb) \; + \; \dots$$ $$=\;\; 2ab \; + \; 2ac \; + \; 2bc \; + \; \dots$$ Here is a way of looking at this that is based on the area of rectangles approach I mentioned above. The full expansion arises from adding all the entries in a Cayley table (i.e. a multiplication table) for a binary operation on the finite set $\{a,\;b,\,c,\;\dots\}$ in which the binary operation is commutative. The Type 1 products are the diagonal entries in the Cayley table and the Type 2 products are the non-diagonal entries in the Cayley table. Because the operation is commutative, the sum of the non-diagonal entries can be obtained by doubling the sum of the entries above the diagonal (or by doubling the sum of the entries below the diagonal).

In (abbreviated) sigma notation we have $$\left(\sum_{i}a_{i}\right)^2 \;\; = \;\; (type \; 1 \; products) \;\; + \;\; (type \; 2 \; products)$$ $$= \;\; \sum_{\begin{array}{c} (i,j) \\ i = j \end{array}} a_{i}a_{j} \;\; + \;\; \sum_{\begin{array}{c} (i,j) \\ i \neq j \end{array}} a_{i}a_{j}$$ $$= \;\; \sum_{\begin{array}{c} (i,j) \\ i = j \end{array}} a_{i}a_{j} \;\; + \;\; 2\sum_{\begin{array}{c} (i,j) \\ i < j \end{array}} a_{i}a_{j}$$ In older advanced "school level" algebra texts from the 1800s, such the texts by George Chrystal and Hall/Knight and Elias Loomis and Charles Smith and William Steadman Aldis and Isaac Todhunter, you can often find the following even more abbreviated notation used: $$(\Sigma)^2 \;\; = \;\;(\Sigma a^2) \; + \; 2(\Sigma ab)$$ In this notation $(\Sigma a^2)$ represents the sum of all expressions $a^2$ where $a$ varies over the terms in the multinomial being squared, and $(\Sigma ab)$ represents the sum of all expressions $ab$ (with $a \neq b$) where $a$ and $b$ vary over the terms in the multinomial being squared (with the selection being "unordered", so that for example once you choose "$b$ and $c$" you don't later choose "$c$ and $b$").

This older notation is especially helpful in stating and using expansions of degree higher than $2$: $$(\Sigma)^3 \;\; = \;\; (\Sigma a^3) \; + \; 3(\Sigma a^2b) \; + \; 6(\Sigma abc)$$ $$(\Sigma)^4 \;\; = \;\; (\Sigma a^4) \; + \; 4(\Sigma a^3b) \; + \; 6(\Sigma a^2b^2) \; + \; 12(\Sigma a^2bc) \; + \; 24(\Sigma abcd)$$ Thus, using the above formula for $(\Sigma)^3$, we can immediately expand $(x+y+z+w)^3$. Altogether, there will be $20$ distinct types of terms: $$(\Sigma a^3) \;\; = \;\; x^3 \; + \; y^3 \; + \; z^3 \; + \; w^3$$ $$3(\Sigma a^2b) \;\; = \;\; 3( x^2y + x^2z + x^2w + y^2x + y^2z + y^2w + z^2x + z^2y + z^2w + w^2x + w^2y + w^2z)$$ $$6(\Sigma abc) \;\; = \;\; 6( xyz \; + \; xyw \; + \; xzw \; + \; yzw)$$

Here is why cubing a multinomial produces the pattern I gave above. By investigating what happens when you multiply $(a+b+c+\dots)$ by the expanded form of $(a+b+c+\dots)^2,$ you'll find that $$(a+b+c+\dots)(a+b+c+\dots)(a+b+c+\dots)$$ can be expanded by adding all individual products of the form

        (term from left) times (term from middle) times (term from right)

The various products that arise can be classifed into the these three types:

Type 1 product: $\;\;$ all $3$ terms are equal to each other

Type 2 product: $\;\;$ exactly $2$ terms are equal to each other

Type 3 product: $\;\;$ all $3$ terms are different from each other

Examples of Type 1 products are $aaa,$ $bbb,$ $ccc,$ etc. Examples of Type 2 products are $aab$ $aba,$ $baa,$ $aac,$ $aca,$ $caa,$ etc. Examples of Type 3 products are $abc,$ $acb,$ $bac,$ $bca,$ $cab,$ $cba,$ etc. Note that each algebraic equivalent of a Type 2 product, such as $a^2b,$ shows up $3$ times, which explains why we multiply $(\Sigma a^2b)$ by $3.$ Also, each algebraic equivalent of a Type 3 product, such as $abc,$ shows up $6$ times, and hence we multiply $(\Sigma abc)$ by $6.$

Those who have understood most things up to this point and who can come up with an explanation for why the $4$th power of a multinomial produces the pattern I gave above (an explanation similar to what I gave for the $3$rd power of a multinomial) are probably now at the point where the Wikipedia article Multinomial theorem can be attempted.

share|improve this answer
    
Actually your post is very helpful. I was still unclear what "i,j pairs" meant until I read your post. (I am only familiar with basic sigma notation) Thanks. –  Denise T Apr 11 '13 at 21:13
    
Very thorough explanation. Thank you. –  Denise T Apr 17 '13 at 1:43

For a set with $a_0=1$ I've organized a nice scheme, which even allows to generalize to infinitly many terms $a_k$ . I don't have that with a general $a_0$ at hand, but maybe this helps you to build it up your own one.
It is for a general (integer) power $p$; if you need it for $p=2$ you can set all terms which contain $(p-2)$ to zero (or ignore them).

enter image description here

Errata: I've just found one typo at he coefficient at $x^4$: instead of $a^3b$ we must have $a^2b$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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