[seqfan] Re: question on a recursively defined sequence
Jim Nastos
nastos at gmail.com
Mon Feb 23 01:26:44 CET 2009
So, once the recursion is written with a single recursive call,
iteration will lead to a "closed form" although
it isn't pretty. In involves towers-of-powers.
t(1) = 1, t(2) = 3
t(3) = 3 + 2^3
t(4) = 3 + 2^3 + 2^3 2^(2^3)
t(5) = 3 + 2^3 + 2^3 2^(2^3) + 2^3 2^(2^3) 2^(2^(2^3))
So, use the function 2Tower(k,N) to mean 2^...^(2^N) where there are k
"2"s written in the tower.
Then t(n) = 3 + SUM (i=1 to n-2) PROD (j=1 to i) 2Tower(i,3)
Tower functions rarely have a way of being expressed without a big-Pi
(product notation.) Most
understandings of "closed form" mean without big-Sigma or big-Pi
notation, so although this gives
a non-recursive formula to calculate the n-th term, it isn't really a
closed form.
I'll agree with Dr. McKay that a closed form is unlikely.
JN
On Sun, Feb 22, 2009 at 4:04 PM, Jim Nastos <nastos at gmail.com> wrote:
> Telescoping once to remove the linear term gives a nicer recurrence
> (only makes one recursive call
> instead of two.) I'm surprised it's not written in the OEIS page.
>
> t(1) = 1
> t(2) = 3
> t(n) = 3 + 2^t(n-1)
>
> Can someone get a closed form from this?
>
> JN
>
>
> On Sun, Feb 22, 2009 at 3:51 PM, T. D. Noe <noe at sspectra.com> wrote:
>> At 3:44 PM -0800 2/22/09, Jonathan Post wrote:
>>>It's on that page thus:
>>>
>>>Closed form of a recursive series
>>>
>>>Is there a closed form with a fixed number of terms for the sequence
>>>defined by t0 = 1 and tn = tn - 1 + 2tn - 1? In case anyone's
>>>wondering, it originates here. NeonMerlin 08:11, 22 February 2009
>>>(UTC)
>>>
>>> I doubt there's anything useful. There's nothing in the Sloane's
>>>entry. Algebraist 09:40, 22 February 2009 (UTC)
>>>
>>>On Sun, Feb 22, 2009 at 3:34 PM, Brendan McKay <bdm at cs.anu.edu.au> wrote:
>>>> At the Mathematics Reference Desk of Wikipedia
>>>> http://en.wikipedia.org/wiki/Wikipedia:Reference_desk/Mathematics
>>>> someone is asking for a closed form for t[n] where
>>>> t[0] = 1, t[n] = t[n-1] + 2^(t[n-1]).
>>>> It looks unlikely to me. Does anyone disagree?
>>
>>
>> Sequence A034797: http://www.research.att.com/~njas/sequences/A034797
>>
>> Tony
>>
>>
>>
>> _______________________________________________
>>
>> Seqfan Mailing list - http://list.seqfan.eu/
>>
>
More information about the SeqFan
mailing list