If you have ever tried making patterns with a collection of coins, you have probably noticed that you can make hexagons in a natural way by packing circles as tightly as possible. The figure below shows how 19 circles fit into a hexagonal shape with 3 circles on each edge. Let H (n) be the number of circles you need to form a hexagon with n circles on each edge. From the figure below, it is clear that H (2) = 7 and H (3) = 19. It can be shown that increasing the number of circles on each edge gives the following recurrence relation: H (n) = 1 if n = 1 H (n - 1) + 6n - 6 if n > 1. Calculate H (9).

We are given the two equations:

H (n) = 1 if n = 1 - - > eqtn 1

H (n) = H (n-1) + 6n - 6 if n>1 - - > eqtn 2

Since we are to find for H (9), so obviously we would use eqtn 2. However take note that in eqtn 2, we have a factor which says H (n-1), this means that we have to calculate also for the value of H (8). However for H (8) we also have to calculate for H (7), therefore we need to calculate all values of H from 8 to 1 also. Let us start from 1:

H (1) = 1

H (2) = 1 + 6 (2) - 6 = 7

H (3) = 7 + 6 (3) - 6 = 19

H (4) = 19 + 6 (4) - 6 = 37

H (5) = 37 + 6 (5) - 6 = 61

H (6) = 61 + 6 (6) - 6 = 91

H (7) = 91 + 6 (7) - 6 = 127

H (8) = 127 + 6 (8) - 6 = 169

H (9) = 169 + 6 (9) - 6 = 217

Therefore the answer is:

H (9) = 217