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 thought about a generalization for the formula $$\frac{x^n - y^n}{x - y} = x^{n - 1} + yx^{n - 2} + \ldots + y^{n - 1}$$ It can be written as $$\frac{x^n - y^n}{x - y} = x^{n - 1} + yx^{n - 2} + \ldots + y^{n - 1} = \sum_{i + j = n - 1}x^iy^j$$

So we would like to generalize: $$\sum_{i_1 + i_2 + i_3 + ... +i_k = n - 1}{x_1}^{i_1}{x_2}^{i_2}{x_3}^{i_3} \cdots {x_k}^{i_k}$$ For example" $$\sum_{i + j + k = n - 1}{x}^{i}{y}^{j}{z}^{k} = \sum_{k=0}^{n - 1}{z}^{k} \sum_{i + j = n - k - 1}{x}^{i}{y}^{j} = \sum_{k=0}^{n - 1}{z}^{k} \frac{x^{n - k} - y^{n - k}}{x -y} = \frac{1}{x-y} \left(\frac{x^{n + 1} - z^{n + 1}}{x - z} - \frac{y^{n + 1} - z^{n + 1}}{y - z}\right)$$

It seems that the generalized expression is the divided difference of $x^{n + k - 2}$ in the points $x_1, x_2, \ldots, x_k$.

Does anyone have an idea how to prove it?

share|improve this question
    
Be careful. $\sum_{k=0}^{n-1} z^k x^{n-k} = x \frac{z^n-x^n}{z-x}$ –  vanna Aug 31 '12 at 12:07
    
I think it's unlikely (but don't let this stop you!). The 2-variable formula you quote is just the homogenization of a 1-variable formula for the sum of a geometric sequence. –  lhf Aug 31 '12 at 12:16
    
vanna - I was right: The sum I wrote is the same sum as k=0 to n, since for k = n we get z^n(1 - 1)/(x - y) = 0 –  darkl Aug 31 '12 at 12:23
    
@DarkL : right. I thought you separated the sums without changing summation to $n$. –  vanna Aug 31 '12 at 12:39
add comment

2 Answers 2

up vote 7 down vote accepted

I think that this formula is what you are looking for. If $\mathbf x = (x_1,\dotsc,x_r)$, then

$$ \sum_{|I|=n} \mathbf{x}^I = \sum_i\frac{x_i^{n}}{\prod_{j\neq i}(1-\frac{x_j}{x_i})}. $$

With 1 variable, it gives $$ x^n = x^n, $$ for two, $$ \sum_{i+j = n} x^i y^j = \frac{x^{n+1}}{x-y} + \frac{y^{n+1}}{y-x}, $$ and for three, if gives $$ \sum_{i+j+k=n} x^i y^j z^k= \frac{x^{n+2}}{(x-y)(x-z)} + \frac{y^{n+2}}{(y-x)(y-z)} + \frac{z^{n+2}}{(z-x)(z-y)}. $$

share|improve this answer
    
Thanks, but can you show how this confirms that the sum is the divided difference of x^(n + k - 1) in the requested points? –  darkl Aug 31 '12 at 13:59
    
@DarkL — Can you explicit what you mean ? –  Lierre Aug 31 '12 at 14:12
    
$$\sum_{i_1 + i_2 + i_3 + ... +i_k = n}{x_1}^{i_1}{x_2}^{i_2}{x_3}^{i_3} \cdots {x_k}^{i_k} = f[x_1, x_2, ..., x_k]$$ where $$f(x) = x^{n + k - 1}$$ and f[,,..,] is the divided difference: see en.wikipedia.org/wiki/Divided_differences –  darkl Aug 31 '12 at 17:27
    
@DarkL — Thanks, I didn't know this notion. But the answer is yes because of the formula (on the wikipage) $f[x_0,\dots,x_n] = \sum_{j=0}^{n} \frac{f(x_j)}{\prod_{k\in\{0,\dots,n\}\setminus\{j\}} (x_j-x_k)}$ –  Lierre Aug 31 '12 at 17:50
add comment

Found a simple proof: in induction:

Assume

$$\sum_{i_1 + i_2 + i_3 + ... +i_k = n}{x_1}^{i_1}{x_2}^{i_2}{x_3}^{i_3} \cdots {x_k}^{i_k} = f[x_1,x_2,..,x_k]$$

For $$f(x) = x^{n + k - 1}$$

For every n.

We'll show $$\sum_{i_1 + i_2 + i_3 + ... +i_k + i_{k + 1} = n}{x_1}^{i_1}{x_2}^{i_2}{x_3}^{i_3} \cdots {x_k}^{i_k}{x_{k+1}}^{i_{k+1}} = g[x_1,x_2,..,x_k,x_{k+1}]$$

where $$g(x) = x^{n + k}$$

Proof: by induction on k: $$\sum_{i_1 + i_2 + i_3 + ... +i_k = n + 1}{x_1}^{i_1}{x_2}^{i_2}{x_3}^{i_3} \cdots {x_k}^{i_k} = g[x_1,x_2,..,x_k]$$ $$\sum_{i_1 + i_2 + i_3 + ... +i_k = n + 1}{x_{k+1}}^{i_1}{x_2}^{i_2}{x_3}^{i_3} \cdots {x_k}^{i_k} = g[x_{k+1},x_2,..,x_k] = g[x_2,..,x_k,x_{k+1}]$$

Then by the definition of the divided difference: $$ g[x_1,..,x_k,x_{k+1}] = \frac{g[x_1,..,x_k] - g[x_2,..,x_k,x_{k+1}]}{x_1 - x_{k+1}}$$

But then

$$g[x_1,..,x_k,x_{k+1}] =$$ $$ \frac{1}{x_1 - x_{k + 1}}\cdot\sum_{i_1 + i_2 + i_3 + ... +i_k = n + 1}\left({x_1}^{i_1}{x_2}^{i_2}{x_3}^{i_3} \cdots {x_k}^{i_k} - {x_{k+1}}^{i_1}{x_2}^{i_2}{x_3}^{i_3} \cdots {x_k}^{i_k}\right) = \sum_{i_1 + i_2 + i_3 + ... +i_k = n + 1}\frac{{x_1}^{i_1} - {x_{k + 1}}^{i_1}}{x_1 - x_{k + 1}} \left({x_2}^{i_2}{x_3}^{i_3} \cdots {x_k}^{i_k} \right)$$ $$ = \sum_{i_1 + i_2 + i_3 + ... +i_k = n + 1}\sum_{j_1 + j_2 = i_1 - 1} {x_1}^{j_1}{x_2}^{i_2}{x_3}^{i_3} \cdots {x_k}^{i_k}{x_{k+1}}^{j_2} $$

$$= \sum_{i_1 + i_2 + i_3 + ... +i_k + i_{k + 1} = n}{x_1}^{i_1}{x_2}^{i_2}{x_3}^{i_3} \cdots {x_k}^{i_k}{x_{k+1}}^{i_{k+1}}$$

That's nice (and directly from the definition), but if someone has a more geometrical explanation for this I'll be glad to hear.

share|improve this answer
add comment

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.