# Finding recurrence relation from an inexact numerical sequence

Consider the recurrence relationship

d[0] = 0;
d[i_] := (1 + Sqrt[1 + 4 d[i - 1]^2])/2 /; i >= 1


which generates the following sequence (generated by using Table[d[i], {i, 0, 50}] // N):

Table1 = {0., 1., 1.61803, 2.19353, 2.74979, 3.29488, 3.8326, 4.36508,
4.89362, 5.4191, 5.94212, 6.46312, 6.98243, 7.50031, 8.01695,
8.53253, 9.04717, 9.56097, 10.074, 10.5864, 11.0982, 11.6095,
12.1203, 12.6306, 13.1405, 13.65, 14.1591, 14.668, 15.1765, 15.6847,
16.1927, 16.7004, 17.2079, 17.7151, 18.2222, 18.729, 19.2357,
19.7422, 20.2485, 20.7547, 21.2607, 21.7666, 22.2724, 22.778,
23.2835, 23.7888, 24.2941, 24.7992, 25.3043, 25.8092, 26.3141}


Can we go in the opposite direction? In other words, is there a way one could find out this underlying recurrence relation (or a good enough approximate recurrence relation by data fitting, etc) in Mathematica given Table1? One could try FindSequenceFunction, but it did not work even after removing the // N as pointed out by @MarcoB in the comment. Any tips/suggestions regarding this will be much appreciated!

• A small clarification: FindSequenceFunction works for exact numerical or symbolic values, and not just integer values. Nevertheless, even after removing the // N from your code, unfortunately FindSequenceFunction can't find a closed-form expression for your sequence. Oct 10 '21 at 22:13
• "or a good enough approximate recurrence relation by data fitting" <- You could use FindFormula, e.g. FindFormula@Partition[Table1, 2, 1]. This produces a linear fit for the recurrence part, which is pretty close to be fair, but I'm not sure if it's useful for you in the context of recursion. It would be interesting to think about implementing a recursion-appropriate cost function for such fitting. Oct 11 '21 at 12:37
• This is a good idea, @Szabolcs , thanks! I will try your suggestion and report the findings in the comment. While in this case I already know the data generating recurrence relation exactly, for the other cases FindFormula-based methods may be a good enough alternative.
– TDH
Oct 11 '21 at 12:51
• @Szabolcs , the fit provided by FindFormula is good enough for my purpose (for the cases where I do not know the recursion in advance). Thanks again!
– TDH
Oct 11 '21 at 13:15
• The problem with fitting only the recursion relation is that the error may become larger and larger as the recursion is applied more and more times. It would make sense to find a formula which minimizes the total error for k recursion steps, instead of just for one recursion step. But I don't think this is possible with FindFormula. If you already have a formula, and just want the parameters, it would be possible with a direct use of NMinimize / FindMinimum. Oct 11 '21 at 13:48