Drum roll please.....
Suppose you have a grid made up of uniformly-spaced horizontal and vertical lines. On the grid you draw a square with corners that lie on some of your grid crossings: it may be a 1x1 square, a 2x2 square, or some other size. How many line (of various sizes) segments from the grid that begin and end on grid crossings are contained in the perimeter and interior your square? What is the answer, in general, for an mxm square?
Lets assume we have an actual grid that exists, say, a 6x6 grid. All squares are even. Now, we'll start by counting the number of segments for a 1x1 square on the given grid, because we're going to use that as our base case in our proof (we'll assume that n \in \doubleN, such that n > 0). In this square, we have 4 segments. In a 2x2 square, we have 18 segments. This is counted by counting every possible concatenated line combination. For a 3x3 square, you'll find 48, for 4x4, 100, and so on. When placed in a table, the pattern is not found, but is found while counting. The number of segments in a given line of length n segments is equivalent to the triangular number, (n(n+1) / 2). We know that there are (n+1) rows in a line of size n. Because its a square, we understand that this value must be multiplied by 2. So, our formula to deduce the number of segments on a grid of size n*n is equal to
= (n(n + 1) / 2)(n+1)(2)
= n(n + 1)^2
Now to prove it...
Let n be an integer, such that n is greater than 0 #an arbitrary number
Assume P(n) is the following predicate:
P(n) = any square with dimensions n*n has n(n + 1)^2
Basis: P(1)
A square with dimensions 1x1 has 4 segments. According to the predicate, the number of segments
= 1(1 + 1)^2 = 4, so P(0) holds.
Induction P(i) --> P(i + 1)
Let i be a natural number
Assume P(i) is true
Then any square with dimensions i*i has i(i + 1)^2 possible segments.
Consider a square of size (i + 1). Its number of possible line combinations of varying lengths is
equivalent to its triangular number. We can prove this by proving the triangular number itself.
its overall number of possible segments can be calculated by multiplying the value by its given
number of rows, i.e. 2(i + 1 + 1). Thus, the number of segments is
= 2(i + 1 + 1) * (i + 1)(i + 1 + 1)/2
= (i + 1)((i + 1) + 1)^2
So if P(i), P(i + 1) holds as well //
Consider a square of size (i + 1). Its number of possible line combinations of varying lengths is
equivalent to its triangular number. We can prove this by proving the triangular number itself.
its overall number of possible segments can be calculated by multiplying the value by its given
number of rows, i.e. 2(i + 1 + 1). Thus, the number of segments is
= 2(i + 1 + 1) * (i + 1)(i + 1 + 1)/2
= (i + 1)((i + 1) + 1)^2
So if P(i), P(i + 1) holds as well //
