Welcome to NRICH.

 
Shape/number pattern
By Brad Rodgers (P1930) on Tuesday, January 23, 2001 - 11:37 pm:

Figures 0,1,2, and 3 consist of 1, 5, 13, and 25 nonoverlapping squares, respectively. If the pattern were continued, how many nonoverlapping unit squares would there be in figure 100?



I've been able to reduce this one to finding a formula for Sn (n=figure number), if

Sn=Sn-1+4n

If you can think up a formula, this should be easy to prove by induction.

Any hints or answers are greatly appreciated.

By Michael Doré (Md285) on Wednesday, January 24, 2001 - 12:50 am:

Your recurrence relationship is correct - well done! To find an explicit form for the sum try to utilise the formula for the nth triangular number:

1 + 2 + ... + n = n(n+1)/2

By Tom Hardcastle (P2477) on Wednesday, January 24, 2001 - 12:52 am:

Consider the shapes placed on a square grid. The width of this grid for shape n must be (1 + 2n). Now look at the squares at the corners that must be removed from this square to form the shape. This consists of a stack of squares, giving 1 + 2 + 3 + ... + n. There is a simple formula for this sum, which is n(n + 1) / 2.
So the number of squares is given by
(1 + 2n)2 - 2n(n+1)
(remember that there are four corners).

Tom.

By Brad Rodgers (P1930) on Wednesday, January 24, 2001 - 01:13 am:

It ends up that the answer is Sn=2n(n+1)+1, giving 20201. Thanks, you've been a great help,

Brad

By The Editor:

An alternative (and easier) method is look at the number of red and green squares in this colouring: