Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Who has hint how to prove: $\sum_{n=0}^N \sum_{k=1}^N g_k y_n = \sum_{n=1}^N \sum_{k=1}^n g_k y_{n-k}+\sum_{n=1}^N\sum_{k=1}^n g_n y_{N-k+1}$

Thank in advance!

share|cite|improve this question
So is $g_{k}$ a sequence, and $y_{n}(x)$ a sequence in $n$, given some parameter $x$? – Daniel Littlewood Nov 20 '12 at 20:42
Now is better. x is not important. I want to prove the summation. – TheStudent Nov 20 '12 at 20:59
I also presume it should be $\sum_{n=1}^{N} \sum_{k=1}^{n} g_{k}y_{n-k}$? – Daniel Littlewood Nov 20 '12 at 21:04
up vote 2 down vote accepted

It's almost always helpful to expand both sides to see where all the terms come from:

LHS: We can factor out $g_{k}$ from the inner sum, since it is independent of both $n$ and $N$. Thus, we have $g_{1}(y_{0}+y_{1}+\ldots+y_{N})+g_{2}(y_{0}+\ldots+y_{N})+\ldots+g_{N}(y_{0}+\ldots +y_{N})$, which we can easily see is $$y_{0}(g_{1}+g_{2}+\ldots+g_{N})+y_{1}(g_{1}+\ldots+g_{N})+\ldots+y_{N}(g_{1}+\ldots+g_{N})$$

RHS: I think your first sum is incorrect; it should read $\sum_{n=1}^{N} \sum_{k=1}^{n} g_{k}y_{n-k}$. If we expand this first sum, where each set of square brackets contains the next value for $n$ (the first set for $n=1$, the next for $n=2$, etc.), we get the following:$[g_{1}y_{0}]+[g_{1}y_{1}+g_{2}y_{0}]+[g_{1}y_{2}+g_{2}y_{1}+g_{3}y_{0}]+\ldots+[g_{1}y_{N-1}+g_{2}y_{N-2}+\ldots g_{N}y_{0}]$
Which, after rearranging, is equal to $y_{0}(g_{1}+g_{2}+\ldots+g_{N})+y_{1}(g_{1}+g_{2}+\ldots+g_{N-1})+\ldots y_{N-1}g_{1}$
Before expanding the second sum, let's see what we have. Each of the $y_{k}$ Has $N-k$ of the terms we want it to be multiplied by. So $y_{0}$ is being multiplied by all the $g_{k}$ we require, $y_{1}$ by all but $g_{N}$, and so on. Let us move onto the second sum.

Expanding similarly, $[g_{1}y_{N}]+[g_{2}y_{N}+g_{2}y_{N-1}]+\ldots+[g_{N}y_{N}+g_{N}y_{N-1}+\ldots g_{N}y_{1}]$. By rearranging, we have $y_{1}g_{N}+y_{2}(g_{N-1}+g_{N})+\ldots+y_{N}(g_{1}+g_{2}+\ldots+g_{N})$

Add the two sums on the RHS and collect your terms, and your identity follows.

share|cite|improve this answer
My proof was not as elegant as proof of @Daniel Littlewood. It was very "flowery" but I think it is intelligible. – MathOverview Nov 20 '12 at 22:40
Thank you! :-) I like your proof too. – Daniel Littlewood Nov 21 '12 at 20:33

We have $$ \begin{align} \sum_{k=1}^N \sum_{n^\prime=0}^N g_k y_n & = \sum_{\substack{1\leq n\leq N\\ 1\leq k \leq N}} g_k y_n \\ & = \sum_{(k,n)\in G} g_k y_n \\ \end{align} $$

Here $G=\{ (k,n) \in\mathbb{N}\times\mathbb{N} : 1\leq n\leq N, 1\leq k \leq N\}$. Set $$ \begin{align} G_1 &=\{ (k,n) \in\mathbb{N}\times\mathbb{N} : 1\leq n\leq k, 1\leq k \leq N, \} \\ & \\ G_2 &= \{ (k,n) \in\mathbb{N}\times\mathbb{N} : k+1\leq n\leq N, 1\leq k \leq N\}.\\ \end{align} $$

Then $G=G_1\cup G_2$, $G_1\cap G_2=\emptyset$ and $$ \begin{align} \sum_{k=1}^N \sum_{n=0}^N g_k y_n & = \sum_{(k,n)\in G} g_k y_n \\ & = \sum_{(k,n)\in G_1} g_k y_n + \sum_{(k,n)\in G_2} g_k y_n \\ & = \sum_{\substack{1\leq n\leq k\\ 1\leq k \leq N}} g_k y_n + \sum_{\substack{k+1\leq n\leq N\\ 1\leq k \leq N}} g_k y_n \\ & = \sum_{1\leq k \leq N}\;\;\sum_{1\leq n\leq k} g_k y_n + \sum_{1\leq k \leq N}\;\;\sum_{k+1\leq n\leq N} g_k y_n \\ & = \sum_{1\leq k \leq N}\;\;\sum_{1\leq n\leq k} g_k y_n + \sum_{1\leq k \leq N}\;\;\sum_{1\leq n-k\leq N-k} g_k y_n \\ \end{align} $$

Making the "change of variables" $n=n^\prime+k$: $$ \begin{align} \sum_{k=1}^N \sum_{n=0}^N g_k y_n & = \sum_{1\leq k \leq N}\;\;\sum_{1\leq n\leq k} g_k y_n + \sum_{1\leq k \leq N}\;\;\sum_{1\leq n^\prime \leq N-k} g_{k^\prime} y_{n^\prime+k} \\ \end{align} $$

The change in notation $n=n^\prime$ does not interfere in the value of the sum we now $$ \begin{align} \sum_{k=1}^N \sum_{n^\prime=0}^N g_k y_n & = \sum_{1\leq k \leq N}\;\;\sum_{1\leq n^\prime\leq k} g_k y_{n^\prime} + \sum_{1\leq k \leq N}\;\;\sum_{1\leq n^\prime \leq N-k} g_{k^\prime} y_{n^\prime+k} \\ \end{align} $$

share|cite|improve this answer

Your Answer


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.