Question

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).

Answer 1

Method 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)=...=61
H(6)=...=91
H(7)=...=127
H(8)=...=169
H(9) = 169+6(9)-6= 217

Method 2:
H(n)=H(n-1)+6n-6
H(n-1)=H(n-2)+6(n-1)-6
H(n-2)=H(n-3)+6(n-2)-6
...
H(3)=H(2)+6(3)-6H(2)
=H(1)+6(2)-6

Sum all lines, and cancel common terms on either side
H(n)=H(1)+6(n+n-1+n-2+...+3+2)-6(n-1)
=H(1)+6(n+2)(n-1)/2-6(n-1)
=H(1)+3n^2-3n    [ after expanding and simplifying ]

This mean that H(9) = H1+3(9^2)-3(9) = 217

if needed, for example, H(123)=1+3(123^2)-3(123)=45019