1
$\begingroup$

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:

The above points plotted on a chart.
On Wolfram Alpha

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

The plot of f(x)=x^sqrt(5)
On Wolfram Alpha

But not exactly:

The above two plots overlayed

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.

$\endgroup$
13
  • 2
    $\begingroup$ $x^{\sqrt{5}}$ is not a polynomial. Do you know the Lagrange interpolation formula? $\endgroup$ – Kevin Sheng Mar 22 '16 at 0:14
  • 2
    $\begingroup$ Using a log-log plot, the last five points fit very well on a power-law function $ \ x^{13/4} \ $ (indeed $ \ \frac{105}{11} \ \approx \ \left( \frac{8}{4} \right)^{13/4} \ $ ) . Unfortunately, the first three points don't work well at all. Using a linear-log plot, the points fit just moderately well to $ \ 2^{(x-1)} \ $ ; the points wander around a straight line. What is the source of the data, and does the phenomenon offer any clue as to what sort of function ought to be manifested? (Sorry,had to revise the exponential fit, which is only so-so...) $\endgroup$ – colormegone Mar 22 '16 at 1:30
  • 2
    $\begingroup$ Then this is not a mere "curve-fitting" problem and the function must match each value exactly. But finding the function is going to require something more like reasoning involving combinatorics, rather than just finding something that passes through all the points (and $ \ n \ $ goes to positive integers beyond $ \ 8 \ $ , with $ \ f(n) \ $ tending to "positive infinity"). [This is why the context of the question is important.] $\endgroup$ – colormegone Mar 22 '16 at 16:53
  • 1
    $\begingroup$ Seconding @RecklessReckoner's comment. This is a perfect example of the XY problem. Create a different question asking about your actual problem, not this curve-fitting. $\endgroup$ – DylanSp Mar 22 '16 at 17:13
  • 1
    $\begingroup$ @BenC.R.Leggiero Ah, I see. That's much clearer; thanks. $\endgroup$ – Théophile Mar 22 '16 at 17:46
2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ A couple more comments: (1) You can see that this is why the cubic approximation that @lulu found in the comments above is such a good fit. (2) You could infer that the function will be cubic by performing successive differences and noticing a pattern. $\endgroup$ – Théophile Mar 22 '16 at 22:31
  • 1
    $\begingroup$ Wow, very nice! This works for every $n > 1$! Then it's trivial to just say 1 is a special case, like $F_0$ $\endgroup$ – Ben Leggiero Mar 23 '16 at 15:34
2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thanks for finding one that goes through all the points! But I'm afraid it might not go through the 9th point. $\endgroup$ – Ben Leggiero Mar 22 '16 at 14:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.