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.

Please can anyone tell me what the below question means and how to solve it:

Observe patterns. Make a conjecture. Prove or disprove.

$$\begin{matrix}1\end{matrix}\qquad\begin{matrix}1 & 1 \\ 1 & 2\end{matrix}\qquad\begin{matrix}1 & 1 & 1\\ 1 & 2 & 2 \\ 1 & 2 & 3\end{matrix}\qquad\begin{matrix}1 & 1 & 1 & 1\\ 1 & 2 & 2 & 2\\ 1 & 2 & 3 & 3 \\ 1 & 2 & 3 & 4\end{matrix}$$

Compute the sum of all numbers in each square array.

share|improve this question
2  
What have you tried? –  lhf Jun 2 '12 at 3:07

5 Answers 5

up vote 8 down vote accepted

The other answers are telling you more-or-less how to solve the question, but it seems that you are also unsure about what the question means. Here is what it means:

  • figure out the pattern in the squares, so that you can correctly draw the fifth, sixth, etc., square.

  • Once you know what the pattern is for the squares, write down the sum of all the numbers in the first square, the second square, etc., and figure out a pattern in those numbers. Typically, this would mean writing down a formula, depending on $n$, whose value at $n$ is equal to the sum of the numbers in the $n$th square.

  • Finally, prove that your formula is correct.

share|improve this answer
    
@ Matt:thanks this explanation was a must for me as I had no idea about these kind of questions! –  mgh Jun 2 '12 at 4:53

Assuming the pattern is $A_{ij}=\min(i,j)+1$

Each number $m$ in the $n \times n$ matrix is written $2(n-m)+1$ times. So we have

$$\sum_{m=1}^n m(2n-2m+1)$$ $$(2n+1)\sum_{m=1}^n m - 2\sum_{m=1}^n m^2$$

If you know the formula for sums of values and sums of squares, then you're golden.

$$=(2n+1)\cdot n(n+1)/2-n(n+1)(2n+1)/3$$ $$=\frac {n(n+1)(2n+1)} 6$$

It's a sum of squares in disguise. Look: each matrix can be expanded as $$\begin{matrix}0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{matrix}+\begin{matrix}0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1\end{matrix}+\begin{matrix}0 & 0 & 0 & 0\\ 0 & 1 & 1 & 1\\ 0 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1\end{matrix}+\begin{matrix}1 & 1 & 1 & 1\\ 1 & 1 & 1 & 1\\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1\end{matrix}$$

which should make that a little more obvious. Each matrix of size $n \times n$ has a sum of squares up to $n$.

share|improve this answer
    
If one already knows the formula for the sums of squares, the exercise seems a bit pointless: in my experience this sort of pictorial exercise is generally used to help students conjecture such formulas, not as finger exercises in their use. –  Brian M. Scott Jun 2 '12 at 5:49
    
I realized the pictorial argument afterward; it probably should have come first. I think it would be unnecessarily difficult to conjecture such a formula from an example like this: recognizing that it's probably a cubic and figuring out the necessary coefficients from a few terms, then proving by induction would probably be a more useful and direct method for coming up with the sum of squares formula itself. I had assumed that the meat of the exercise was in the 'prove' point, rather than the 'conjecture' point, where the use (either visually or symbolically) is more relevant. –  Robert Mastragostino Jun 2 '12 at 14:24

The first pattern that might come to mind is this:

$$\begin{matrix}\underline{1}\end{matrix}\qquad\begin{matrix}1 & \underline{1} \\ \underline{1} & \underline{2}\end{matrix}\qquad\begin{matrix}1 & 1 & \underline{1}\\ 1 & 2 & \underline{2} \\ \underline{1} & \underline{2} & \underline{3}\end{matrix}\qquad\begin{matrix}1 & 1 & 1 & \underline{1}\\ 1 & 2 & 2 & \underline{2}\\ 1 & 2 & 3 & \underline{3} \\ \underline{1} & \underline{2} & \underline{3} & \underline{4}\end{matrix}$$

Each array simply adds a ‘shell’ to the previous one, around the righthand side and the bottom. You can make some progress with this pattern, though it’s not the most helpful one: if you add up the new (underlined) bits in each array, you get $1,4,9,16$, which is recognizable as $1^2,2^2,3^2,4^2$. Now the problem suggests computing the sums of the numbers in each array. If we let $s_n$ be the sum of the numbers in the $n$-th array, we have

$$\begin{align*} s_1&=1^2\\ s_2&=1^2+2^2\\ s_3&=1^2+2^2+3^2\\ s_4&=1^2+2^2+3^2+4^2 \end{align*}$$

It seems pretty clear that these arrays have something to do with sums of consecutive squares. Unfortunately, it’s not clear what, and it’s not obvious that the added ‘shells’ will continue to be consecutive squares. Is there any other way to break up the arrays that involves sums of consecutive squares?

Yes: think of the arrays as representing three-dimensional arrangements of cubical blocks. We’re looking down on them from above, and each number stands for a stack of that many blocks. Thus, the first array represents a single cubical block. The second represents a square of four blocks with a fifth square stacked atop the one in the lower righthand corner; using $\square$ for an empty space and $\blacksquare$ for a blocks, I could ‘draw’ the arrangement like this, where the lefthand side represents the bottom layer of the arrangement and the righthand side, the second layer.

$$\begin{array}{c} \blacksquare\;\blacksquare&\qquad\qquad&\square\;\square\\ \blacksquare\;\blacksquare&\qquad\qquad&\square\;\blacksquare \end{array}$$

Notice that this just stacks the first arrangment on top of the lower righthand corner of a $2\times 2$ square of blocks.

A similar breakdown by layers (from bottom to top) of the arrangement of blocks represented by the third array looks like this:

$$\begin{array}{c} \blacksquare\;\blacksquare\;\blacksquare&\qquad\qquad&\square\;\square\;\square&\qquad\qquad&\square\;\square\;\square\\ \blacksquare\;\blacksquare\;\blacksquare&\qquad\qquad&\square\;\blacksquare\;\blacksquare&\qquad\qquad&\square\;\square\;\square\\ \blacksquare\;\blacksquare\;\blacksquare&\qquad\qquad&\square\;\blacksquare\;\blacksquare&\qquad\qquad&\square\;\square\;\blacksquare \end{array}$$

This just stacks the second arrangement on top of the lower righthand corner of a $3\times 3$ square of blocks. Similarly, it’s not hard to see that the fourth arrangement stacks the third on the lower righthand corner of a $4\times 4$ square of blocks:

$$\begin{array}{c} \blacksquare\;\blacksquare\;\blacksquare\;\blacksquare&\qquad\qquad&\square\;\square\;\square\;\square&\qquad\qquad&\square\;\square\;\square\;\square&\qquad\qquad&\square\;\square\;\square\;\square\\ \blacksquare\;\blacksquare\;\blacksquare\;\blacksquare&\qquad\qquad&\square\;\blacksquare\;\blacksquare\;\blacksquare&\qquad\qquad&\square\;\square\;\square\;\square&\qquad\qquad&\square\;\square\;\square\;\square\\ \blacksquare\;\blacksquare\;\blacksquare\;\blacksquare&\qquad\qquad&\square\;\blacksquare\;\blacksquare\;\blacksquare&\qquad\qquad&\square\;\square\;\blacksquare\;\blacksquare&\qquad\qquad&\square\;\square\;\square\;\square\\ \blacksquare\;\blacksquare\;\blacksquare\;\blacksquare&\qquad\qquad&\square\;\blacksquare\;\blacksquare\;\blacksquare&\qquad\qquad&\square\;\square\;\blacksquare\;\blacksquare&\qquad\qquad&\square\;\square\;\square\;\blacksquare \end{array}$$

When you think about the arrays in this fashion it really is clear that the $n$-th array is just adding a layer of $n^2$ blocks under the $(n-1)$-st array, so that $s_n=1^2+2^2+3^2+\ldots+n^2$, as we suspected from the first pattern.

It may well be that this is all that you were supposed to notice; it would be difficult, for instance, to conjecture a formula for $s_n$ on the basis of these figures. If you already know that formula, $$s_n=\frac{n(n+1)(2n+1)}6\;,\tag{1}$$ the exercise seems to me fairly pointless, but you can finish it off by observing that since we now know that $s_n$ is the sum of the first $n$ squares, we know that $s_n$ is given by $(1)$.

If not, there are other patterns that you could see, though none that I consider particularly useful. For instance, you could break each array down into the ‘shells’ on the left and top consisting of identical numbers. I’ll use the sixth array as an example.

$$\begin{array}{c} 1&1&1&1&1&1\\ 1&2&2&2&2&2\\ 1&2&3&3&3&3\\ 1&2&3&4&4&4\\ 1&2&3&4&5&5\\ 1&2&3&4&5&6 \end{array}$$

There are $11$ $1$’s, $9$ $2$’s, $7$ $3$’s, $5$ $4$’s, $3$ $5$’s, and $1$ $6$:

$$\begin{array}{r} k:&1&&2&&3&&4&&5&&6\\ \text{Number of }k\text{’s}:&11&&9&&7&&5&&3&&1\\ \hline \text{Total}:&11&+&18&+&21&+&20&+&15&+&6&=&91 \end{array}$$

It’s not hard to see that in general the $n$-th array can be broken down similarly into $2n-1$ $1$’s, $2n-3$ $2$’s, and so on down to $1$ $n$. Thus, if we write down the numbers from $1$ through $n$, and under them the odd numbers from $1$ through $2n-1$ in reverse order, multiply the numbers in each column, and add the products across the bottom, we’ll get $s_n$, the sum of the first $n$ squares. For $n=7$, for instance, we get:

$$\begin{array}{r} 1&&2&&3&&4&&5&&6&&7\\ 13&&11&&9&&7&&5&&3&&1\\ \hline 13&+&22&+&27&+&28&+&25&+&18&+&7&=&140 \end{array}$$

This pattern isn’t very useful $-$ it doesn’t help us to calculate $s_n$ any more easily than by adding up the successive squares, for instance $-$ but it’s a real pattern in this sequence of arrays, one that can be formulated precisely and whose reality can be proved rigorously.

share|improve this answer

Look at the fourth square. The sum of the numbers in row 3 is equal to the sum of row 4 minus 1. The sum of row 2 is the sum of row 4 minus 3. The sum of row 1 is the sum of row 4 minus 5. Do you see a pattern now?

share|improve this answer

Notice what the difference is between each successive square. The second square is the first square plus a row and column. The third square, again, is the second square plus a row and a column. Those new rows and columns follow a simple pattern. In the second square, we're adding 1, 2, 1. In the third square, we're adding 1, 2, 3, 2, 1. And so on. The intuition should be clear that these new terms we are adding each time sum to $n^2$, with $n$ being the number of rows (or columns) in the square.

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.