My Math Forum Number of Squares proof

 Algebra Pre-Algebra and Basic Algebra Math Forum

 February 2nd, 2013, 08:00 PM #1 Member   Joined: May 2012 Posts: 86 Thanks: 0 Number of Squares proof A square with side length n is divided into n^2 equal squares. Prove by induction that the total number of squares (of any side length) in this array is equal to (n(n+1)(2n+1))/6 Help is appreciated
 February 2nd, 2013, 09:32 PM #2 Global Moderator     Joined: Oct 2008 From: London, Ontario, Canada - The Forest City Posts: 7,958 Thanks: 1146 Math Focus: Elementary mathematics and beyond Re: Number of Squares proof $n\,=\,2\,\Rightarrow\,\frac{n(n\,+\,1)(2n\,+\,1)}{ 6}\,=\,5\text{ and }\frac{n(n\,+\,1)(2n\,+\,1)}{6}\,+\,(n\,+\,1)^2\,= \,14$ $\frac{n(n\,+\,1)(2n\,+\,1)}{6}\,+\,(n\,+\,1)^2\,=\ ,\frac{2n^3\,+\,9n^2\,+\,13n\,+\,6}{6}$ $\frac{(n\,+\,1)(n\,+\,2)(2(n\,+\,1)\,+\,1)}{6}\,=\ ,\frac{2n^3\,+\,9n^2\,+\,13n\,+\,6}{6}$
February 3rd, 2013, 04:06 AM   #3
Math Team

Joined: Oct 2011

Posts: 14,597
Thanks: 1038

Re: Number of Squares proof

Quote:
 Originally Posted by Jakarta (n(n+1)(2n+1))/6
That's the standard sum of squares formula.

February 3rd, 2013, 08:30 AM   #4
Member

Joined: Jan 2013

Posts: 93
Thanks: 0

Re: Number of squares proof

Quote:
 Originally Posted by Jakarta A square with side length n is divided into n^2 equal squares. Prove by induction that the total number of squares (of any side length) in this array is equal to (n(n+1)(2n+1))/6
The inductive step is as follows.

Consider an $(n+1)\times(n+1)$ grid of squares obtained by adding to an $n\times n$ grid an extra column on the right and an extra row at the top. This creates:

$2(n+1)-1$ additional $1\times1$ squares
$2n-1$ additional $2\times2$ squares
• $\vdots$
$2\cdot2-1$ additional $n\times n$ squares
$2\cdot1-1$ additional $(n+1)\times(n+1)$ square

Total number of additional squares is
• $\sum_{r=1}^{n+1}(2r-1)$
$=2\sum_{r=1}^{n+1}r-(n+1)$

$=(n+1)(n+2)-(n+1)$

$=(n+1)^2$

The number of squares of all sizes in the original $n\times n$ grid is $\frac{n(n+1)(2n+1)}{6}$ by the inductive hypothesis.

Hence total number of squares of all sizes in the $(n+1)\times(n+1)$ grid is $\frac{n(n+1)(2n+1)}{6}+(n+1)^2$ which greg1313 has shown is equal to $\frac{(n+1)([n+1]+1)(2[n+1]+1)}{6}$.

Verify that the formula is true for $n=1$ and you’re done.

 Tags number, proof, squares

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post jjvivde Real Analysis 1 January 8th, 2014 11:05 PM MrBibbles Number Theory 4 July 25th, 2013 06:46 AM thenight Complex Analysis 1 March 27th, 2013 02:50 AM icemanfan Number Theory 2 November 15th, 2012 08:41 AM momesana Algebra 1 March 13th, 2010 03:16 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top