----------------
Summations
So, chapter 1 was about recurrent problems, but chapter 2 is about summations, which are like more general recurrences that use a different notation. They're an indispensable, elegant notation created by Leibniz, who independently created calculus at the same time as Newton. Despite his contributions, he died alone, a broken man in an unmarked grave. Remember kids, few things guarantee happiness.
 |
| POUR ONE OUT FOR OUR MAN LEIBNIZ |
The main points we have to look forward to in this post, are how to put problems in terms of summations, how to manipulate summations, and some of their intrinsic properties that let us take shortcuts with dank identities.
Notation
The tricky parts are the unspoken implications. Using Concrete Mathematics's notation, guess what the following means:
$$\sum_k a_k$$
That's exactly right, it means sum $a_k$ for all integers $k$, i.e. $a_0 + a_1 + a_{-1} + a_2 + a_{-2} ... $, excellent guess. I totally missed the assumption that, without setting the index, that we're spanning the whole range of integers, not just natural numbers.
Let's survey some examples.
$\sum_{P(k)} a_k$
means that summing over all integers $k$ for which condition $P(k)$ is true.
Ok, a more sane one.
$\sum_{i=0}^n i = 0 + 1 + 2 + ... + n-1 + n$
This summation describes the sum of $1..n$, which is equivalent to the recurrence $R_n = R_{n-1} + n, R_0 = 0$
Let's use inequalities to describe the same thing
$\sum_{1\leq k \leq n} k$
Finally, try to guess this tricky one before looking at the answer.
$\sum_{0 \leq k^2 \leq 5} k$
----------------
blank space to encourage trying the problem
----------------
Right, so remember we're sampling k from the set of all integers, so we're only taking k for values when the condition in the inequality is true. In other words, all integers $k$ where $0 \leq k^2 \leq 5$, which is
$k=-{2}, {-1}, 0, 1, 2$
In other words, this summation expanded is...
$\sum_{0 \leq k^2 \leq 5} k = {-2} + {-1} + 0 + 1 + 2 = 0$
That's pretty much as tricky as they'll get. These notations just express the ideas, so play with them and expand them to get a better sense when you're working through problems.
$$\sum_k a_k$$
That's exactly right, it means sum $a_k$ for all integers $k$, i.e. $a_0 + a_1 + a_{-1} + a_2 + a_{-2} ... $, excellent guess. I totally missed the assumption that, without setting the index, that we're spanning the whole range of integers, not just natural numbers.
Let's survey some examples.
$\sum_{P(k)} a_k$
means that summing over all integers $k$ for which condition $P(k)$ is true.
Ok, a more sane one.
$\sum_{i=0}^n i = 0 + 1 + 2 + ... + n-1 + n$
This summation describes the sum of $1..n$, which is equivalent to the recurrence $R_n = R_{n-1} + n, R_0 = 0$
Let's use inequalities to describe the same thing
$\sum_{1\leq k \leq n} k$
Finally, try to guess this tricky one before looking at the answer.
$\sum_{0 \leq k^2 \leq 5} k$
----------------
blank space to encourage trying the problem
----------------
Right, so remember we're sampling k from the set of all integers, so we're only taking k for values when the condition in the inequality is true. In other words, all integers $k$ where $0 \leq k^2 \leq 5$, which is
$k=-{2}, {-1}, 0, 1, 2$
In other words, this summation expanded is...
$\sum_{0 \leq k^2 \leq 5} k = {-2} + {-1} + 0 + 1 + 2 = 0$
That's pretty much as tricky as they'll get. These notations just express the ideas, so play with them and expand them to get a better sense when you're working through problems.
Sums and Recurrences
Right, so since this is chapter 2, we're not just throwing away all our knowledge from chapter 1. They're the same kind of animal, and we're going to show how we can convert between them.
Recall the tower of hanoi recurrence.
$$T_0 = 0 \\ T_n = 2T_{n-1} + 1$$
This would be a bit tricky to immediately express as a recurrence, so we want to simplify it by having the coefficients to the recurrent terms make sense recursively.
$$T_0 = 0 \\ \frac{T_n}{2^n} = \frac{T_{n-1}}{2^{n-1}} + \frac{1}{2^n}$$
Now the $T_n$ terms have matching coefficients and we can simplify this expression with the alias
$S_n = \frac{T_n}{2^n}, S_0 = 0$
and get the recurrence
$S_n = S_{n-1} + \frac{1}{2^n}$
which is much easier to convert into a summation.
$S_n = \sum_{i=1}^{n} s^{-i} = 1 - {1/2}^n$
and since we know the relation between $S_n$ and $T_n$, we can convert this to a summation for $T_n$
$T_n = 2^n \cdot S_n = 2^n - 1$
All of that was relatively straightforward sans figuring out what to multiply the equation by to get the recurrent terms to match. It's actually more straightforward than you think. We'll consider this problem for history 1 recurrences of the form.
$a_n T_n = b_n T_{n-1} + c_n$
in order for the recurrences to "match" every time, we need to multiply by some value $s$ such that $sb_n = sa_{n-1}$. $s$ will usually need to be dependent on all previous values, so we'll call the $s$ for the n'th recurrence relation $s_n$. In other words $s_n b_n = s_{n-1} a_{n-1}$
This will allow us to write
$a_n s_n T_n = s_n b_n T_{n-1} + s_n c_n = s_{n-1} b_{n-1} T_{n-1} + s_n c_n $
and so the coefficients in front of the recurrent terms once again "match" for their respective values of n, and we can substitute $S_n = a_n s_n T_n$ and get
$S_n = S_{n-1} + s_{n} c_{n}$
Which is clearly a summation like our initial example.
Ok, so know what we want the value to do, but how do we get it?
Well, we know by definition that
$$s_n = \frac{s_{n-1} a{n-1}}{b_n} \\ = \frac{a_{n-1}}{b_n} \cdot \frac{s_{n-1} a_{n-2}}{b_{n-1}}$$
and we follow that all the way down the rabbit hole until we hit the base case. In other words
$$s_n = \frac{s_{n-1} a{n-1}}{b_n} = \frac{a_{n-1}}{b_n} \cdot \frac{s_{n-1} a_{n-2}}{b_{n-1}} = ... = \frac{a_{n-1} a_{n-2} ... a_{2}a_{1}}{b_{n}b_{n-1}...b_{3}b_{2}}$$
This is one of those things you should spend 5 minutes working out to prove to yourself before moving on.
----------------
Let's convert a slightly more tricky recurrence to a sum.
$$T_0 = 5 \\
2T_n=nT_{n-1} + 3 \cdot n! \quad \text{for } n>0$$
Recall we want $s_n$ such that $s_nT_n = ns_nT_{n-1} + 3n! = a_n T_n = a_{n-1} + 3 n!$
In this case, $s_n = \frac{2\cdot2...2}{n\cdot{(n-1)}...2} = \frac{2^{n-1}}{n!}|$
and this indeed gets us
$\frac{2^n}{n!}T_n = \frac{2^{n-1}}{(n-1)!}T_n + 2^n 3$
So now let's substitute $S_n = \frac{2^n}{n!}T_n$ and we'll see that
$S_n = S_{n-1} + 3 \cdot 2^{n-1}$
Which is just begging to be summed
$S_n = 5 + \sum_{k=1}^{n} 3\cdot 2^{k-1} = 5 + 3(2^{n} - 1)$
So now we convert the $S_n$ sum to $T_n$
$T_n = \frac{n!}{2^n} S_n$
i..e
$T_n = \frac{n!}{2^n} (5 + 3(2^n - 1)) = \frac{(3\cdot 2^b + 2) n!}{2^n} = n!(3 + 2^{1-n})$
Bada bing bada boom, there's one hot solution!
Once you get a handle on sums, you have more techniques to solve them than recurrences!
Recall the tower of hanoi recurrence.
$$T_0 = 0 \\ T_n = 2T_{n-1} + 1$$
This would be a bit tricky to immediately express as a recurrence, so we want to simplify it by having the coefficients to the recurrent terms make sense recursively.
$$T_0 = 0 \\ \frac{T_n}{2^n} = \frac{T_{n-1}}{2^{n-1}} + \frac{1}{2^n}$$
Now the $T_n$ terms have matching coefficients and we can simplify this expression with the alias
$S_n = \frac{T_n}{2^n}, S_0 = 0$
and get the recurrence
$S_n = S_{n-1} + \frac{1}{2^n}$
which is much easier to convert into a summation.
$S_n = \sum_{i=1}^{n} s^{-i} = 1 - {1/2}^n$
and since we know the relation between $S_n$ and $T_n$, we can convert this to a summation for $T_n$
$T_n = 2^n \cdot S_n = 2^n - 1$
All of that was relatively straightforward sans figuring out what to multiply the equation by to get the recurrent terms to match. It's actually more straightforward than you think. We'll consider this problem for history 1 recurrences of the form.
$a_n T_n = b_n T_{n-1} + c_n$
in order for the recurrences to "match" every time, we need to multiply by some value $s$ such that $sb_n = sa_{n-1}$. $s$ will usually need to be dependent on all previous values, so we'll call the $s$ for the n'th recurrence relation $s_n$. In other words $s_n b_n = s_{n-1} a_{n-1}$
This will allow us to write
$a_n s_n T_n = s_n b_n T_{n-1} + s_n c_n = s_{n-1} b_{n-1} T_{n-1} + s_n c_n $
and so the coefficients in front of the recurrent terms once again "match" for their respective values of n, and we can substitute $S_n = a_n s_n T_n$ and get
$S_n = S_{n-1} + s_{n} c_{n}$
Which is clearly a summation like our initial example.
Ok, so know what we want the value to do, but how do we get it?
Well, we know by definition that
$$s_n = \frac{s_{n-1} a{n-1}}{b_n} \\ = \frac{a_{n-1}}{b_n} \cdot \frac{s_{n-1} a_{n-2}}{b_{n-1}}$$
and we follow that all the way down the rabbit hole until we hit the base case. In other words
$$s_n = \frac{s_{n-1} a{n-1}}{b_n} = \frac{a_{n-1}}{b_n} \cdot \frac{s_{n-1} a_{n-2}}{b_{n-1}} = ... = \frac{a_{n-1} a_{n-2} ... a_{2}a_{1}}{b_{n}b_{n-1}...b_{3}b_{2}}$$
This is one of those things you should spend 5 minutes working out to prove to yourself before moving on.
----------------
Let's convert a slightly more tricky recurrence to a sum.
$$T_0 = 5 \\
2T_n=nT_{n-1} + 3 \cdot n! \quad \text{for } n>0$$
Recall we want $s_n$ such that $s_nT_n = ns_nT_{n-1} + 3n! = a_n T_n = a_{n-1} + 3 n!$
In this case, $s_n = \frac{2\cdot2...2}{n\cdot{(n-1)}...2} = \frac{2^{n-1}}{n!}|$
and this indeed gets us
$\frac{2^n}{n!}T_n = \frac{2^{n-1}}{(n-1)!}T_n + 2^n 3$
So now let's substitute $S_n = \frac{2^n}{n!}T_n$ and we'll see that
$S_n = S_{n-1} + 3 \cdot 2^{n-1}$
Which is just begging to be summed
$S_n = 5 + \sum_{k=1}^{n} 3\cdot 2^{k-1} = 5 + 3(2^{n} - 1)$
So now we convert the $S_n$ sum to $T_n$
$T_n = \frac{n!}{2^n} S_n$
i..e
$T_n = \frac{n!}{2^n} (5 + 3(2^n - 1)) = \frac{(3\cdot 2^b + 2) n!}{2^n} = n!(3 + 2^{1-n})$
Bada bing bada boom, there's one hot solution!
Once you get a handle on sums, you have more techniques to solve them than recurrences!
Manipulation of Sums
Fundamentally, we only have 3 basic tricks we're legally allowed, all of which are simple and obvious.
$$\sum_{k \in K} c \cdot a_k = c \sum_{k \in K} a_k \text{(distributive law)} \\
\sum_{k \in K} {(a_k + b_k)} = \sum_{k \in K}{a_k} + \sum_{k \in K}{b_k}\text{(associative law)} \\
\sum_{k \in K} a_k = c \sum_{p(k) \in K} a_{p(k)} \text{(commutative law)}$$
where $p(k)$ is a permutation of K
The commutative law is the least clear in notation, but it really just means that we can expand our sum and re-arrange it, but so long as all the elements are the same, the sum itself is unchanged. The technique of arranging low and high values in the classic summation of $1 + 2 + ... + n$ is seen as an application of this.
Let's do a problem just using these principles.
Recall that $\sum_{k=0}^{n} 2^k = 2^{n+1} - 1$. We now want to generalize this by finding a closed form for $\sum_{k=0}^{n} x^k$, and we're going to do it by using some basic association.
$$\sum_{k=0}^{n} x^k + x^{n+1} = \sum_{k=0}^{n+1} x^{k} = x^{0} + \sum_{k=1}^{n+1} x^{k} = 1 + \sum_{k=0}^{n}x^{{k+1}} = 1 + x \cdot \sum_{k=0}^{n}x^{{k}}$$
now we can rearrange and solve for the sum
$$ \sum_{k=0}^{n} x^k - x \cdot \sum_{k=0}^{n}x^{{k}} = 1 - x^{n+1}\\
= (1-x)\sum_{k=0}^{n} x^k = 1 - x^{n+1}\ , \ \\
\sum_{k=0}^{n} x^k = \frac{1 - x^{n+1}}{1-x} = \frac{x^{n+1} - 1}{x - 1}
$$
Nice, we got a closed form with nothing but basic operations. Let's try doing this again but for solving $□_n = \sum_{k=0}^{n} k^2$
$$□_n + (n+1)^2 = \sum_{k=0}^{n+1} k^2 = 0^2 + \sum_{k=1}^{n+1} k^2 = \sum_{k=0}^{n} (k+1)^2\\
= \sum_{k=0}^{n} (k^2 + 2k + 1) = \sum_{k=0}^{n}k^2 + \sum_{k=0}^{n}2k + \sum_{k=0}^{n}1 \\
\Rightarrow □_n - \sum_{k=0}^{n} k^2 + (n+1)^2 = \sum_{k=0}^{n} 2k + (n+1)$$
the $□_n - \sum_{k=0}^{n} k^2 $ cancels out so we lose the term we were trying to find, but if we continue
$$(n+1)^2 = \sum_{k=0}^{n} 2k + (n+1)\\
\Rightarrow \ \sum_{k=0}^{n} 2k = n^2 + 2n + 1 - n - 1 = 2\sum_{k=0}^{n} k = n^2 + n \\
\Rightarrow \ \sum_{k=0}^{n} k = \frac{n^2 + n }{2} = \frac{n(n+1)}{2} \quad$$
then we get the closed form for the sum of 1..n, which means that we can get equations for the sums of lower powers using this method. Let's try doing the same thing for $\sum_{k=0}^{n}k^3$
$$\sum_{k=0}^{n}k^3 + (n+1)^3 = \sum_{k=0}^{n}(k+1)^3 = \sum_{k=0}^{n}(k^3 + 3k^2 + 3k + 1) \\
= \sum_{k=0}^{n}(k^3) + \sum_{k=0}^{n}(3k^2) + \sum_{k=0}^{n}(3k) + \sum_{k=0}^{n}(1) \\ = \sum_{k=0}^{n}k^3 + 3\sum_{k=0}^{n}k^2 + 3\cdot \frac{n^2 + n}{2} + n+1$$
So we have an equation with the $\sum_{k=0}^{n}(k^2)$ in it! Let's get rid of the $\sum_{k=0}^{n}(k^3)$ terms and simplify our expression.
$$\sum_{k=0}^{n}k^3 - \sum_{k=0}^{n}k^3 + (n+1)^3 = 3\sum_{k=0}^{n}k^2+ 3\cdot \frac{n^2 + n}{2} + n+1 \\
\Rightarrow \ 3\sum_{k=0}^{n}k^2 = (n+1)^3 - 3\cdot \frac{n^2 + n}{2} - n - 1 = n^3 + 3n^2 + 2n - 3\cdot \frac{n^2 + n}{2}\\
= \frac{2n^3 + 6n^2 + 4n - 3n^2 - 3n}{2} = \frac{2n^3 + 3n^2 + n}{2}\\
\Rightarrow \ \sum_{k=0}^{n}k^2 = \frac{2n^3 + 3n^2 + n}{6} = \frac{n(n+1)(2n+1)}{6} = \frac{n(n+\frac{1}{2})(n+1)}{3}$$
Finally, we arrive at the closed form to our summation.
As always, don't be afraid to play around; ultimately, you won't know what the right way to permute and associate the sums until you're done!
$$\sum_{k \in K} c \cdot a_k = c \sum_{k \in K} a_k \text{(distributive law)} \\
\sum_{k \in K} {(a_k + b_k)} = \sum_{k \in K}{a_k} + \sum_{k \in K}{b_k}\text{(associative law)} \\
\sum_{k \in K} a_k = c \sum_{p(k) \in K} a_{p(k)} \text{(commutative law)}$$
where $p(k)$ is a permutation of K
The commutative law is the least clear in notation, but it really just means that we can expand our sum and re-arrange it, but so long as all the elements are the same, the sum itself is unchanged. The technique of arranging low and high values in the classic summation of $1 + 2 + ... + n$ is seen as an application of this.
Let's do a problem just using these principles.
Recall that $\sum_{k=0}^{n} 2^k = 2^{n+1} - 1$. We now want to generalize this by finding a closed form for $\sum_{k=0}^{n} x^k$, and we're going to do it by using some basic association.
$$\sum_{k=0}^{n} x^k + x^{n+1} = \sum_{k=0}^{n+1} x^{k} = x^{0} + \sum_{k=1}^{n+1} x^{k} = 1 + \sum_{k=0}^{n}x^{{k+1}} = 1 + x \cdot \sum_{k=0}^{n}x^{{k}}$$
now we can rearrange and solve for the sum
$$ \sum_{k=0}^{n} x^k - x \cdot \sum_{k=0}^{n}x^{{k}} = 1 - x^{n+1}\\
= (1-x)\sum_{k=0}^{n} x^k = 1 - x^{n+1}\ , \ \\
\sum_{k=0}^{n} x^k = \frac{1 - x^{n+1}}{1-x} = \frac{x^{n+1} - 1}{x - 1}
$$
Nice, we got a closed form with nothing but basic operations. Let's try doing this again but for solving $□_n = \sum_{k=0}^{n} k^2$
$$□_n + (n+1)^2 = \sum_{k=0}^{n+1} k^2 = 0^2 + \sum_{k=1}^{n+1} k^2 = \sum_{k=0}^{n} (k+1)^2\\
= \sum_{k=0}^{n} (k^2 + 2k + 1) = \sum_{k=0}^{n}k^2 + \sum_{k=0}^{n}2k + \sum_{k=0}^{n}1 \\
\Rightarrow □_n - \sum_{k=0}^{n} k^2 + (n+1)^2 = \sum_{k=0}^{n} 2k + (n+1)$$
the $□_n - \sum_{k=0}^{n} k^2 $ cancels out so we lose the term we were trying to find, but if we continue
$$(n+1)^2 = \sum_{k=0}^{n} 2k + (n+1)\\
\Rightarrow \ \sum_{k=0}^{n} 2k = n^2 + 2n + 1 - n - 1 = 2\sum_{k=0}^{n} k = n^2 + n \\
\Rightarrow \ \sum_{k=0}^{n} k = \frac{n^2 + n }{2} = \frac{n(n+1)}{2} \quad$$
then we get the closed form for the sum of 1..n, which means that we can get equations for the sums of lower powers using this method. Let's try doing the same thing for $\sum_{k=0}^{n}k^3$
$$\sum_{k=0}^{n}k^3 + (n+1)^3 = \sum_{k=0}^{n}(k+1)^3 = \sum_{k=0}^{n}(k^3 + 3k^2 + 3k + 1) \\
= \sum_{k=0}^{n}(k^3) + \sum_{k=0}^{n}(3k^2) + \sum_{k=0}^{n}(3k) + \sum_{k=0}^{n}(1) \\ = \sum_{k=0}^{n}k^3 + 3\sum_{k=0}^{n}k^2 + 3\cdot \frac{n^2 + n}{2} + n+1$$
So we have an equation with the $\sum_{k=0}^{n}(k^2)$ in it! Let's get rid of the $\sum_{k=0}^{n}(k^3)$ terms and simplify our expression.
$$\sum_{k=0}^{n}k^3 - \sum_{k=0}^{n}k^3 + (n+1)^3 = 3\sum_{k=0}^{n}k^2+ 3\cdot \frac{n^2 + n}{2} + n+1 \\
\Rightarrow \ 3\sum_{k=0}^{n}k^2 = (n+1)^3 - 3\cdot \frac{n^2 + n}{2} - n - 1 = n^3 + 3n^2 + 2n - 3\cdot \frac{n^2 + n}{2}\\
= \frac{2n^3 + 6n^2 + 4n - 3n^2 - 3n}{2} = \frac{2n^3 + 3n^2 + n}{2}\\
\Rightarrow \ \sum_{k=0}^{n}k^2 = \frac{2n^3 + 3n^2 + n}{6} = \frac{n(n+1)(2n+1)}{6} = \frac{n(n+\frac{1}{2})(n+1)}{3}$$
Finally, we arrive at the closed form to our summation.
As always, don't be afraid to play around; ultimately, you won't know what the right way to permute and associate the sums until you're done!
Multiple Sums
We go over multiple sums after the "manipulation of sums" section because, really, they're pretty much the same thing as regular sums. In-fact, we can represent double-sums as individual sums, and vica-versa.
Here's some basic notation
$\sum_{1\leq i,j \leq k}^{3} a_{ij} = a_{11} + a_{12} + a_{13}
\\ \quad \quad \quad \quad \ \ \ + \ a_{21} + a_{22}+ a_{23}
\\ \quad \quad \quad \quad \ \ \ + \ a_{31} + a_{32} + a_{33} $
for this sum we're saying both i and j are between 1 and 3
But a more common form of a double summation will include 2 variables
$$\sum_{0\leq i \leq j \leq k}^{n} a_{ij}= \sum_{i=0}^{n}\sum_{j=i}^{n} a_{ij}$$
which for n=3, would look like
$\sum_{1\leq i,j \leq k}^{3} a_{ij} = \ a_{11} + a_{12} + a_{13}
\\ \quad \quad \quad \quad \quad \quad \quad \quad + a_{22}+ a_{23}
\\ \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \ \ + a_{33} $
Usually when we evaluate multiple sums, we work from the inner-most loop first, with the outer-summations being iterated every time our inner summations finish. When our indices are independent, we can interchange inner and outer loops.
$$\sum_{j=1}^{n} \sum_{k=j}^{n} a_{j,k} = \sum_{1\leq j \leq k \leq n} a_{j,k} = \sum_{k=1}^{n} \sum_{j=1}^{k} a_{j,k}$$
We should convince ourselves that these two summations are equivalent by analyzing that the inequalities are equivalent using iversonian notation.
$$[1 \leq j \leq n][j \leq k \leq n] = [1 \leq k \leq n][1\leq j \leq k]$$
This may not be enough, and in my opinion, the most important thing you can do with respect to Multiple sums is to try to visualize them. The author suggests, and to do that you should really just write them out. Here's a visualization of the interchange, found in sums_and_summations.c here.
Let's do a problem involving this concept, by writing a single summation as a double summation!
$$\sum_{k=1}^{n}{k \cdot 2^{k}} = \sum_{1\leq j \leq k \leq n}^{n}2^{k}$$
If we do this in a vanilla fashion, we write it as
$$\sum_{j=1}^n \sum_{k=j}^n 2^{k}$$
we can apply our summation-swap identity
$$\sum_{k=1}^n \sum_{j=1}^k 2^{k} = \sum_{k=1}^n k2^k $$
which at least proves to us that it works. However, what we really want to do to this problem, is to visualize it. If you write out the terms in a matrix of i and j indices.
We find that we can make an easier sum by completing the sum in the form of $n2^{n+1}$ and summing the negative terms. That is
Here's some basic notation
$\sum_{1\leq i,j \leq k}^{3} a_{ij} = a_{11} + a_{12} + a_{13}
\\ \quad \quad \quad \quad \ \ \ + \ a_{21} + a_{22}+ a_{23}
\\ \quad \quad \quad \quad \ \ \ + \ a_{31} + a_{32} + a_{33} $
for this sum we're saying both i and j are between 1 and 3
But a more common form of a double summation will include 2 variables
$$\sum_{0\leq i \leq j \leq k}^{n} a_{ij}= \sum_{i=0}^{n}\sum_{j=i}^{n} a_{ij}$$
which for n=3, would look like
$\sum_{1\leq i,j \leq k}^{3} a_{ij} = \ a_{11} + a_{12} + a_{13}
\\ \quad \quad \quad \quad \quad \quad \quad \quad + a_{22}+ a_{23}
\\ \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \ \ + a_{33} $
Usually when we evaluate multiple sums, we work from the inner-most loop first, with the outer-summations being iterated every time our inner summations finish. When our indices are independent, we can interchange inner and outer loops.
$$\sum_{j=1}^{n} \sum_{k=j}^{n} a_{j,k} = \sum_{1\leq j \leq k \leq n} a_{j,k} = \sum_{k=1}^{n} \sum_{j=1}^{k} a_{j,k}$$
We should convince ourselves that these two summations are equivalent by analyzing that the inequalities are equivalent using iversonian notation.
$$[1 \leq j \leq n][j \leq k \leq n] = [1 \leq k \leq n][1\leq j \leq k]$$
This may not be enough, and in my opinion, the most important thing you can do with respect to Multiple sums is to try to visualize them. The author suggests, and to do that you should really just write them out. Here's a visualization of the interchange, found in sums_and_summations.c here.
Let's do a problem involving this concept, by writing a single summation as a double summation!
$$\sum_{k=1}^{n}{k \cdot 2^{k}} = \sum_{1\leq j \leq k \leq n}^{n}2^{k}$$
If we do this in a vanilla fashion, we write it as
$$\sum_{j=1}^n \sum_{k=j}^n 2^{k}$$
we can apply our summation-swap identity
$$\sum_{k=1}^n \sum_{j=1}^k 2^{k} = \sum_{k=1}^n k2^k $$
which at least proves to us that it works. However, what we really want to do to this problem, is to visualize it. If you write out the terms in a matrix of i and j indices.
 |
| Red means "doesn't exist" in the normal summation, so we subtract the red terms |
We find that we can make an easier sum by completing the sum in the form of $n2^{n+1}$ and summing the negative terms. That is
We easily figure out the sum just from writing it out and visualizing it.
you could see a generael version of this problem where the 2 becomes any base and you take the differences in the form of the geometric sums.
Finite and Infinite Calculus
"Finite Calculus" might sound weird, but the point of it is to create techniques for summations that get us their closed forms, similar in fashion to the rules we use to do integration.
To start off, we must define a discrete difference operator that operates on a function $f$.
$$\Delta f(x) = f(x+1) - f(x)$$
Which is the same as the calculus difference operator $\frac{f(x+h) - f(x)}{h}$, except that $h$ is simply 1 instead of approaching 0.
In context of the summation operator:
$$\sum g(x) \delta x = f(x) + c, \quad \text{iff}\quad g(x) = \Delta f(x)$$
Except here, $\sum g(x) \delta x$ is the indefinite sum of $g(x)$; that is, it is the class of functions whose difference is $g(x)$
With an analogous definite integral, we have
$$\sum_a^{b} g(x) \delta x = f(x) |^b_a = f(b) - f(a)$$
If we assume b is actually a+1, we get
$$\sum_a^{a+1} g(x) \delta x = f(a+1) - f(a) = g(a)$$
If we increase b by one,w e have
$$\sum_{a}^{b+a}g(x) \delta x - sum_a^n g(x)\delta x = (f(b+1) - f(a)) + (f(b) - f(a)) = f(b+1) - f(b) = g(b)$$
If we induct these observations, we can figure out that in general, when $b\geq a$
$$\sum_a^{a+1} g(x) \delta x = \sum_{k=a}^{b-1} g(k)$$
That is, the definite sum is the same as a normal sum but excluding the value of the upper limit.
Anyway, we're here for tricks. What are some implications of this analogy? Well, we can have a sort of skewed version of the power rule in the form of falling powers. That is, we have
$$x^{\underline{m}} = x (x-1) (x-2) ... (x-m+1)$$
which has a nice property, that
$$\Delta x^{\underline{m}} = m,\quad \text{for} m \neq \{-1,0\} $$
I suggest the reader prove this for themselves (it's not hard!). With this power, if we write summations in terms of the rising and falling powers, we can compute them easily.
$$\sum_{k=0}^{n} k^2 = \sum_{k=0}^{n} k^{\underline{2}} + k^{\underline{1}} = \frac{ k^{\underline{3}}}{3} + \frac{ k^{\underline{2}}}{2} = \frac{1}{3}n(n-1)(n-2) + \frac{1}{2}n(n-1) = \frac{1}{3} n (n-\frac{1}{2})(n-1)$$
Now, if we replace $n$ with $n+1$, as per definition of the definite sum, we get yet another way to compute $\sum_{k=0}^{n} k^2$
To start off, we must define a discrete difference operator that operates on a function $f$.
$$\Delta f(x) = f(x+1) - f(x)$$
Which is the same as the calculus difference operator $\frac{f(x+h) - f(x)}{h}$, except that $h$ is simply 1 instead of approaching 0.
In context of the summation operator:
$$\sum g(x) \delta x = f(x) + c, \quad \text{iff}\quad g(x) = \Delta f(x)$$
Except here, $\sum g(x) \delta x$ is the indefinite sum of $g(x)$; that is, it is the class of functions whose difference is $g(x)$
With an analogous definite integral, we have
$$\sum_a^{b} g(x) \delta x = f(x) |^b_a = f(b) - f(a)$$
If we assume b is actually a+1, we get
$$\sum_a^{a+1} g(x) \delta x = f(a+1) - f(a) = g(a)$$
If we increase b by one,w e have
$$\sum_{a}^{b+a}g(x) \delta x - sum_a^n g(x)\delta x = (f(b+1) - f(a)) + (f(b) - f(a)) = f(b+1) - f(b) = g(b)$$
If we induct these observations, we can figure out that in general, when $b\geq a$
$$\sum_a^{a+1} g(x) \delta x = \sum_{k=a}^{b-1} g(k)$$
That is, the definite sum is the same as a normal sum but excluding the value of the upper limit.
Anyway, we're here for tricks. What are some implications of this analogy? Well, we can have a sort of skewed version of the power rule in the form of falling powers. That is, we have
$$x^{\underline{m}} = x (x-1) (x-2) ... (x-m+1)$$
which has a nice property, that
$$\Delta x^{\underline{m}} = m,\quad \text{for} m \neq \{-1,0\} $$
I suggest the reader prove this for themselves (it's not hard!). With this power, if we write summations in terms of the rising and falling powers, we can compute them easily.
$$\sum_{k=0}^{n} k^2 = \sum_{k=0}^{n} k^{\underline{2}} + k^{\underline{1}} = \frac{ k^{\underline{3}}}{3} + \frac{ k^{\underline{2}}}{2} = \frac{1}{3}n(n-1)(n-2) + \frac{1}{2}n(n-1) = \frac{1}{3} n (n-\frac{1}{2})(n-1)$$
Now, if we replace $n$ with $n+1$, as per definition of the definite sum, we get yet another way to compute $\sum_{k=0}^{n} k^2$
Summing By Parts
Finally, discrete calculus offers us a way to rewrite our sums in a "by parts" version.
If we define first
$Ef(x) = f(x+1)$
then we can see that
$\Delta (uv) = u \Delta v + Ev\Delta u$
which we can rearrange and then apply a summation to, i.e.
$\sum u \Delta v = uv - \sum Ev \Delta u$
We can then place limits on the terms to make definite integrals.
General Methods
Alright, so let's consolidate our sum and recurrence knowledge so far into a set of methods we can use to dive-tackle any problem that wants a piece of the old noggin.
$\int_{k=0}^{n}k^2dk = k^3/3$
Then we get something that's very close to our answer, but not quite there. However it lets us know that our sum has a cubic polynomial as its largest term.
Though integrating your sum probably won't give you the exact answer, it'll give you something quite similar to the form of your answer, which can be used to build on and solve the problem. This is useful for building repertoires where you guess the form of your function, or perhaps just figuring it out directly after seeing the hint and then probing it with induction. Using calculus to create hints, who knew!
Method 0 : Look up the Answer
There's a good chance that the problem you're working on has been solved before, so we can find the solution using any number of resources like google, oeis.com, Wolfram Alpha, Mathematics, or "the CRC Standard Mathematical Table". Ultimately, you do this not to return a numeric value, but to help gain intuition about a series you're looking for, so it's a bit of a red herring in this list, but one that shouldn't just be dismissed when you need some intuition now.Method 1 : Prove By Induction
We used this in the last chapter(did we?). We gain some cosmic bolt of insight and start to convince ourselves that the closed form of a summation looks like some function $f(x)$. We
Method 2 : Perturb the Sum
This is the name of associative technique we were using in the "Manipulation of Sums" section. It's mostly a trick rather than a general approach, but it's one that you can do fairly quickly as a starting point to your problem.Method 3 : Build a Repertoire
Building a repertoire isn't just about using the repertoire method, but about recognizing common summations that can be used as bases, as well as previous problems that are similar or can be used as some building block. Ultimately, the repertoire method is about understanding how to combine your previous experiences to solve your current problems.Method 4 : Replace Sums by Integrals
Ever wanted to know what the sum $\sum_{k=0}^{n}k^2$ is? Gosh, me too all the time. If we tried computing$\int_{k=0}^{n}k^2dk = k^3/3$
Then we get something that's very close to our answer, but not quite there. However it lets us know that our sum has a cubic polynomial as its largest term.
Though integrating your sum probably won't give you the exact answer, it'll give you something quite similar to the form of your answer, which can be used to build on and solve the problem. This is useful for building repertoires where you guess the form of your function, or perhaps just figuring it out directly after seeing the hint and then probing it with induction. Using calculus to create hints, who knew!
Method 5 : Expand and Contract
Really, this is the same as playing around with sums, except we might choose to contract only a portion of our expanded sum and mess around with our notation in more novel ways. Consider doing things like going from a single sum to a double sum, or a double sum to a triple sum. As long as you try to be creative, you'll find some way to massage your sum into a more convenient form.Method 6 : Use Finite Calculus
By recognizing the form of the definite sum, as well as some of the tricks from the section, we can manipulate our sums without doing any real computation by taking advantage of this higher layer of abstraction that is finite calcululs. This method may not get you all the way to a solution, but it's very powerful for rewriting your problem in more comprehensible forms.Method 7 : Use Generating Functions
"Stay tuned for still more exciting calculations of $□_n = \sum_{k=0}^{n}k^2$ as we learn further techniques in the next section and later chapters." - Literally What the Book Says About This MethodIn conclusion, I think that summations, more than recurrences, are a topic that you just need to do a lot of problems in until you get some really solid intuition about these techniques and their meaning. Never get stuck in one mindset or method when you're solving a problem, but rather be creative in warping it and picking it apart because that's when it's fun.
No comments :
Post a Comment