The source of this problem is this SPOJ question.
Let me simplify it:
A valid beehive is recursively defined as follows:
1. A single regular hexagon is a valid beehive.
2. To all the external cells of a valid beehive, a regular hexagon can be attached to each of it's sides and the result will also be a valid beehive. (An external cell means a regular hexagon on the outer layer whose some sides are not adjacent to any other hexagon.)
Given the number of hexagons you need to say whether it can form a valid beehive or not.
By manually working it out, I found that the number of hexagons in beehives of each stage follows this order,$$1,7,19,37,61…$$
The general formula for this which I think satisfies the pattern is $$3n(n-1)+1$$
However I couldn't figure out a complete logical explanation for this.
This is how far I have worked it out,
At each stage every external hexagon has 3 free sides, with the exception of the first stage in which there is only one hexagon therefore all six sides are free. However, two hexagon's contribute a side to a same resulting hexagon. Out of the three free sides, two are shared with others to form a hexagon. Therefore if there are $n$ external hexagons there will be $n+n/2$ new hexagons. However, this does not satisfy the later stages.
Would be great if someone could give a complete logical explanation for this.
Best Answer
Starting with $n_1:=1$ you have $n_{i+1}=n_i+6i$ because you'll adding a hexagon whose six edges each consist of $i+1$ cells, but the ones in the corners belong to two edges so you only count them half each time.
This confirms your claim for the first few elements of the sequence, can be computed quickly, and leads to A003215. OEIS gives the formula as $3n(n+1)+1$ but they have an index shift: their $n_0$ is my $n_1$. If you plug $n-1$ instead of $n$ in that equation, you get $3(n-1)n+1$ which is what you obtained yourself, so that ist correct as well.
This is where you went wrong: most external hexagons have two free sides, the only exception being those in the corners.