How do I find a (polynomial?) function given 8 points on a graph?

Question

I know the following are true for my problem:

• $f(1) = 1$
• $f(2) = 2$
• $f(3) = 5$
• $f(4) = 11$
• $f(5) = 22$
• $f(6) = 40$
• $f(7) = 67$
• $f(8) = 105$
• ...
• $f(x) =\;?$ where $x \in{\mathbb{Z}_{\geq 0}}$

When plotted, I get the following:

^{On Wolfram Alpha}

This looks to me like it's hyperbolic, and almost maps to $f(x) = x^\sqrt{5}$:

^{On Wolfram Alpha}

But not exactly:

I can't quite grasp the solution. How do I find the function upon which these points and further ones in their pattern lie? The solution doesn't have to be a polynomial; I just don't have all my schooling knowledge needed to find other kinds of solutions.

Answer 1

Given a board with side length $n$, the total number of groups is $$f(n) = S(n) + L(n)$$ where $S$ is the number of $1\times1$ groups (Small) and $L$ is the number of $2\times2$ or bigger groups (Large). It turns out that $$S(n) = (n-1)^2 + 1 = n^2-2n+2,$$ which you can prove by compacting the dark and (interior) light squares to make an $(n-1)\times(n-1)$ square with one square left over. As for $L$, note that the groups of size $2\times2$ or greater are precisely the subsquares that do not touch the outer edge. There is $1$ biggest subsquare (with side length $n-2$), there are $2^2=4$ subsquares with side length $n-3$, and so on, up to $(n-3)^2$ subsquares with side length $2$. Therefore we have $$\begin{align} L(n) &= 1^2+2^2+\ldots+(n-3)^2\\ &=\frac{(n-3)((n-3)+1)(2(n-3)+1)}6\\ &=\frac{(n-3)(n-2)(2n-5)}6. \end{align}$$ Combining these expressions and simplifying,

$$f(n) = S(n)+L(n) = \frac{2n^3-9n^2+25n-18}6$$

except for $n=1$, for which we have, of course, $f(1)=1$. (The above counting argument doesn't work for $n=1$ because of the small size of the board.)

Answer 2

The polynomial function \begin{equation} f(x) = \frac{-x^7}{5040}+\frac{x^6}{144}-\frac{73x^5}{720}+\frac{115x^4}{144}-\frac{299}{90}x^3+\frac{295}{36}x^2-\frac{2011}{210}x\ +\ 5 \end{equation} Passes through all the points you listed. Its shape may not be what your looking for, but this is the unique polynomial of degree 7 that passes through the points you listed. If you want it to pass through the origin then an 8th degree polynomial is required. Given $n$ points on a graph, there exist a unique polynomial function of degree $n-1$ that pass through said points. You can solve for a polynomial passing through $n$ points by making a linear system and solving it with Gaussian elimination. We know that the general 7th degree polynomial function has the form \begin{equation} f(x) = a_1x^7 + a_2x^6 + a_3x^5 + a_4x^4 + a_5x^3 + a_6x^2 + a_7x + a_8 \end{equation} where $a_1, \ldots, a_7$ are constants. We then use your conditions \begin{align} f(1) = a_1 + a_2 + a_3 + a_4 + a_5 + a_6 + a_7 + a_8 &= 1\\ f(2) = 128a_1 + 64a_2 + 32a_3 + 16a_4 + 8a_5 + 4a_6 + 2a_7 + a_8 &= 2\\ f(3) = 2187a_1 + 729a_2 + 243a_3 + 81a_4 + 27a_5 + 9a_6 + 3a_7 + a_8 &= 5\\ &\vdots\\ f(8) = 2097152a_1 + 262144a_2 + 32768a_3 + 4096a_4 + 512a_5 + 64a_6 + 8a_7 + a_8 &= 105 \end{align} You now have 8 equations and 8 unknowns. You can use your method of choice for solving linear systems in order the find the coefficients. For such a large system, Gaussian elimination will be easier to use then substitution or Cramer's method.