I ended yesterday's post by suggesting that the recursive relation for the sum of powers of consecutive integers could be proven by means of mathematical induction. It turns out that this by no means seems trivial or natural; indeed a much more straightforward and natural approach is to use the geometric intuition that suggested the relation in the first place.
First we define some terms that will be used in the proof.
The cell $C_{i,j}$ for positive integers $i,j$ is the square region in $\mathbb{R}^2$ given by $\{(x,y) \in \mathbb{R}^2 | (i-1) \leq x < i $, $ (j-1) \leq y < j\}$. The box $C_{i,j,k}$ for positive integers $i,j,k$ is the cubic region in $\mathbb{R}^3$ given by $\{(x,y,z) \in \mathbb{R}^3 | (x,y)\in C_{i,j}$, $ (k-1) \leq z < k \}$. As the reader can see, cells partition the first quadrant of the plane, and boxes partition the first octant of $3$-space. For a positive integer $n$, we define the $n$-pyramid $P_n$ to be the set of boxes $C_{i,j,k}$ satisfying $i\leq n$, $j \leq n$ and $k \leq min(i,j)$. The $m$th level ($1\leq m \leq n$) of the pyramid $P_n$ is simply $\{C_{i,j,k} \in P_n | k=n-m+1\}$. This agrees more or less with the notion of an $n$-pyramid from the previous post, and I will spare the reader from trivial geometric verifications of the fact that the $m$th level contains $m^2$ boxes, among other things. Recall that the impetus for thinking about this pyramid is that the total number of boxes (given simply by counting level by level) is $\sum_{i=1}^n i^2.$
We also let $S_k(n)=\sum_{i=0}^n i^k$, in line with the notation used in the previous post. Now we can state and prove the main theorem.
Theorem. $S_k(n)=\sum_{i=0}^n(S_{k-2}(n)-S_{k-2}(i))(2i+1)$ for integers $k \geq 2$ and $n \geq 0$.
Proof. We divide each box into $m^{k-2}$ compartments (where $m$ is the level of the box). Then $S_k(n)$ gives the total number of compartments in the pyramid. Consider the cell $C_{l,l}$. This cell has $l$ boxes above it (since $min(l,l)=l$), given by $\{C_{l,l,k}| 1\leq k \leq l \}$. Also note that all cells $C_{l,m}$ and $C_{m,l}$ with $m > l$ have l boxes above them (since in either case $min(m,l)=min(l,m)=l$). In each case the boxes occupy levels $(n-l+1), (n-l+2), \ldots , n$, and so each of these cells has the same number of compartments above it as $C_{l,l}$.
We can define an equivalence relation between the cells, such that two cells $C_{i,j} \sim C_{k,m}$ if and only if they have the same number of compartments above them. In light of the preceding discussion, it is easy to see that $C_{i,j} \sim C_{k,m}$ if and only if $min(i,j)=min(k,m)$. This relation partitions the $n^2$ cells at the base of the pyramid into $n$ disjoint equivalence classes, and we can take the diagonal cell $C_{i,i}$ as a representative of the $2(n-i)+1$ cells in each class.
The total number of compartments above cell $C_{i,i}$ is $n^{k-2}+(n-1)^{k-2}+\cdots+(n-i+1)^{k-2}=S_{k-2}(n)-S_{k-2}(n-i),$ and so the total number of compartments above each equivalence class is $(S_{k-2}(n)-S_{k-2}(n-i))(2(n-i)+1)$. The total number of compartments in the pyramid is then given by:
$\sum_{i=1}^{n} (S_{k-2}(n)-S_{k-2}(n-i))(2(n-i)+1) = \sum_{i=0}^{n} (S_{k-2}(n)-S_{k-2}(i))(2i+1),$ as desired.
The cell $C_{i,j}$ for positive integers $i,j$ is the square region in $\mathbb{R}^2$ given by $\{(x,y) \in \mathbb{R}^2 | (i-1) \leq x < i $, $ (j-1) \leq y < j\}$. The box $C_{i,j,k}$ for positive integers $i,j,k$ is the cubic region in $\mathbb{R}^3$ given by $\{(x,y,z) \in \mathbb{R}^3 | (x,y)\in C_{i,j}$, $ (k-1) \leq z < k \}$. As the reader can see, cells partition the first quadrant of the plane, and boxes partition the first octant of $3$-space. For a positive integer $n$, we define the $n$-pyramid $P_n$ to be the set of boxes $C_{i,j,k}$ satisfying $i\leq n$, $j \leq n$ and $k \leq min(i,j)$. The $m$th level ($1\leq m \leq n$) of the pyramid $P_n$ is simply $\{C_{i,j,k} \in P_n | k=n-m+1\}$. This agrees more or less with the notion of an $n$-pyramid from the previous post, and I will spare the reader from trivial geometric verifications of the fact that the $m$th level contains $m^2$ boxes, among other things. Recall that the impetus for thinking about this pyramid is that the total number of boxes (given simply by counting level by level) is $\sum_{i=1}^n i^2.$
We also let $S_k(n)=\sum_{i=0}^n i^k$, in line with the notation used in the previous post. Now we can state and prove the main theorem.
Theorem. $S_k(n)=\sum_{i=0}^n(S_{k-2}(n)-S_{k-2}(i))(2i+1)$ for integers $k \geq 2$ and $n \geq 0$.
Proof. We divide each box into $m^{k-2}$ compartments (where $m$ is the level of the box). Then $S_k(n)$ gives the total number of compartments in the pyramid. Consider the cell $C_{l,l}$. This cell has $l$ boxes above it (since $min(l,l)=l$), given by $\{C_{l,l,k}| 1\leq k \leq l \}$. Also note that all cells $C_{l,m}$ and $C_{m,l}$ with $m > l$ have l boxes above them (since in either case $min(m,l)=min(l,m)=l$). In each case the boxes occupy levels $(n-l+1), (n-l+2), \ldots , n$, and so each of these cells has the same number of compartments above it as $C_{l,l}$.
We can define an equivalence relation between the cells, such that two cells $C_{i,j} \sim C_{k,m}$ if and only if they have the same number of compartments above them. In light of the preceding discussion, it is easy to see that $C_{i,j} \sim C_{k,m}$ if and only if $min(i,j)=min(k,m)$. This relation partitions the $n^2$ cells at the base of the pyramid into $n$ disjoint equivalence classes, and we can take the diagonal cell $C_{i,i}$ as a representative of the $2(n-i)+1$ cells in each class.
The total number of compartments above cell $C_{i,i}$ is $n^{k-2}+(n-1)^{k-2}+\cdots+(n-i+1)^{k-2}=S_{k-2}(n)-S_{k-2}(n-i),$ and so the total number of compartments above each equivalence class is $(S_{k-2}(n)-S_{k-2}(n-i))(2(n-i)+1)$. The total number of compartments in the pyramid is then given by:
$\sum_{i=1}^{n} (S_{k-2}(n)-S_{k-2}(n-i))(2(n-i)+1) = \sum_{i=0}^{n} (S_{k-2}(n)-S_{k-2}(i))(2i+1),$ as desired.
Posts
No comments:
Post a Comment