2
$\begingroup$

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!

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ 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. $\endgroup$
    – MarcoB
    Oct 10 '21 at 22:13
  • 2
    $\begingroup$ "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. $\endgroup$
    – Szabolcs
    Oct 11 '21 at 12:37
  • $\begingroup$ 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. $\endgroup$
    – TDH
    Oct 11 '21 at 12:51
  • $\begingroup$ @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! $\endgroup$
    – TDH
    Oct 11 '21 at 13:15
  • $\begingroup$ 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. $\endgroup$
    – Szabolcs
    Oct 11 '21 at 13:48

Your Answer

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

Browse other questions tagged or ask your own question.