# Given f[1] … f[k], k = 1, 2, 3… how do one find the general function f[n]?

If I have that

f[1] = 2 a b;
f[2] = 2 a b (1 + 6 a);
f[3] = 2 a b (1 + 9 a + 12 a^2);
f[4] = 2 a b (1 + 21 a + 72 a^2 + 60 a^3);
f[5] = 2 a b (1 + 45 a + 300 a^2 + 600 a^3 + 360 a^4);
f[6] = 2 a b (1 + 93 a + 1080 a^2 + 3900 a^3 + 5400 a^4 + 2520 a^5);
f[7] = 2 a b (1 + 189 a + 3612 a^2 + 21000 a^3 + 50400 a^4 + 52920 a^5 + 20160 a^6);


etc, how can I find a rule for $f(n)$ ?

-
Does it have anything to do with Mathematica? – Öskå Jul 27 '14 at 18:54
I hope that mathematica can solve this problem, but I don't know how. – Maya Jul 27 '14 at 19:06
FindGeneratingFunction and FindSequenceFunction do this, but they probably won't work for such a general symbolic sequence. – Szabolcs Jul 27 '14 at 19:21
Can you give some idea as to where these formulas are coming from? Perhaps the origin will help illuminate the pattern of the sequence. I doubt Mathematica can divine the pattern without additional input. – Mr.Wizard Jul 27 '14 at 23:43
InterpolatingPolynomial[{2a b,2a b(1+6a),2a b(1+9a+12a^2),2a b(1+21a+72a^2+60a^3),2a b(1+45a+300a^2+600a^3+360a^4),2a b(1+93a+1080a^2+3900a^3+5400a^4+2520a^5)},x]//Simplify – mathe Jul 28 '14 at 0:37

The following answer is based on the assumption that you made a mistake in your opening post and that the term f[2] = 2 a b (1 + 6 a) is actually supposed to be f[2] = 2 a b (1 + 3 a), i.e. with a 3 replacing the 6.

Let's first concentrate on the coefficients. Later we can easily construct the polynomials from them. The following image illustrates the pattern behind the coefficients:

To describe this pattern, let $(k,n)$ denote the $k^\mathrm{th}$ coefficient in the $n^\mathrm{th}$ row. Each row starts with a one, i.e. $(1,n)=1$ for all $n$. The last coefficient is always equal to the last of the previous row multiplied by $n+1$. Thus $(n,n)=(n-1,n-1)\cdot(n+1)$ for all $n\neq1$. The ones in between are constructed by

$$(k,n)=k\cdot(k,n-1)+(k+1)\cdot(k-1,n-1).$$

I used Fold to implement this sequence. You can see that I used the above rules for the First and Last elements of each iteration. The ones in between are computed in the Table.

coefficients[n_Integer] :=
Fold[Join[
{First@#1},
Table[k #1[[k]] + (k + 1) #1[[k - 1]], {k, 2, #2}],
{(#2 + 2) Last@#1}] &,
{1},
Range[n - 1]]


And indeed this creates the same coefficients as in your opening post (again with the 6 replaced by 3).

Grid[coefficients /@ Range@7]
(*
1
1   3
1   9   12
1   21  72  60
1   45  300 600 360
1   93  1080    3900    5400    2520
1   189 3612    21000   50400   52920   20160 *)


Now, the polynomials can be created with FromDigits:

f[n_Integer] :=
2 a b Expand@FromDigits[Reverse@coefficients@n, a]


Finally, test with some n:

f[11]
(*
2 a (1 + 3069 a + 342012 a^2 + 8745000 a^3 + 88822800 a^4 +
452307240 a^5 + 1289977920 a^6 + 2155507200 a^7 + 2095632000 a^8 +
1097712000 a^9 + 239500800 a^10) b *)


For those inclined to terse coding the coefficients function could be written as:

g[1] := {1}

g[n_] := g[n - 1] /. {x__} :> ({0, x} (# + 1) + {x, 0} # & @ Range[n])


Test:

g[7]

{1, 189, 3612, 21000, 50400, 52920, 20160}

-
Nice catch! :) +1 – Öskå Jul 30 '14 at 21:01
And nice work finding and illustrating a pattern. +1! – Mr.Wizard Jul 31 '14 at 4:56
@Mr.Wizard Thanks for the edit! I knew someone would come up with a more concise way to code it. I'm not surprised it's you! :) – einbandi Jul 31 '14 at 16:16
You're welcome. :D – Mr.Wizard Jul 31 '14 at 16:19
@einbandi Wow, wow, wow. You are a genius :) I am impressed. Thank You very much. Yes, it was mistake, 6 should be replaced with 3. I apologize for the confusion. Thanks again :) – Maya Aug 1 '14 at 23:36

Using the insight from einbandi just another way to produce pattern:

fun[u_] := Module[{lg},
lg = Length[u];
PadLeft[u Range[3, lg + 2], lg + 1] + PadRight[u Range[lg], lg + 1]]

pol[v_] := (a^Range[0, Length@v - 1]).v


Nesting:

grd = Grid[
Transpose[{TraditionalForm[f[#]] & /@ Range[1, 7],
HoldForm[2 a b  #] & /@ (pol /@ NestList[fun, {1}, 6])}],
Alignment -> Left, Frame -> {{True, True}, None},
Background -> {None, {{LightBlue, White}}}]


-