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 = 1H(n - 1) + 6n - 6 if n > 1.
Calculate H(6).