Math Question

Math Question

Anomie

Member #9,403

January 2008

$<math>f(1) = 1 + 1^2 = 2</math>$
$<math>f(n) = f(n-1) + f(n-1)^2</math>$

Is there some reasonable way to get the correct answer for any whole n > 0 without using recursion?

______________
I am the Lorax. I speak for the trees. I speak for the trees for the trees have no tongues.

Evert

Member #794

November 2000

Probably. You should be able to write it using a binomial expansion, although I can't work it out without taking pen and paper to hand.
I doubt it'll make it easier though.

Wetimer

Member #1,622

November 2001

Untested:

int x = 1;
for(int y = 0; y < n; y++)
{
    x = x + x*x;
}

Technically it is not recursion although it sounds like you might be wanting a closed form solution.

<code>if(Windows.State = Crash) Computer.halt();</code>

Anomie

Member #9,403

January 2008

I don't know anything about doing binomial expansion with arguments to a function, and I couldn't find anything about it...would you mind elaborating?

[edit]

Quote:

Technically it is not recursion although it sounds like you might be wanting a closed form solution.

Yeah, sorry for not mentioning that earlier. I'm looking for a 'non-iterative' solution.

______________
I am the Lorax. I speak for the trees. I speak for the trees for the trees have no tongues.

Wetimer

Member #1,622

November 2001

Hmm... if you try expanding it by hand for the first few times, you'll find the terms increasing rapidly. I suspect you could find a pattern that will enable you to quickly derive the formula for the final result, however I don't think it'll be easier to calculate...

<code>if(Windows.State = Crash) Computer.halt();</code>

Anomie

Member #9,403

January 2008

Yeah, it accelerates really quickly.

f(1) = 2
f(2) = 6
f(3) = 42
f(4) = 1,806
f(5) = 3,263,442
f(6) = 10,650,056,950,806
f(7) = 113,423,713,055,421,844,361,000,442
f(8) = 12,864,938,683,278,671,740,537,145,998,360,961,546,653,259,485,195,806

But I can't see any other obvious patterns.

______________
I am the Lorax. I speak for the trees. I speak for the trees for the trees have no tongues.

Evert

Member #794

November 2000

First of all, you probably need to think in terms of a sequence of numbers $<math>f_n</math>$ rather than a function $<math>f(n)</math>$ . Minor difference, but anyway.

It's a tricky little bugger. The closest I could come was (taking $<math>f_0 = 1</math>$ as a given)
$<math>f_n = f_{n-1}(1+f_{n-1}) = f_{n-2}(1+f_{n-2})(1+f_{n-1}) = \cdots = \prod_{k=1}^{n-1} (1+f_k) = \prod_{k=1}^{n-1} ( 1+\prod_{m=1}^{k-1} (1+\cdots f_1)</math>$
which doesn't really solve the problem unless you can eliminate the repeated products, which I thought you could do with a binomial expansion, but I don't really see how. On a helpful note, you can use the expansion I gave to verify any explicit formula you come up with by induction.
Aside, this sequence grows astoundingly fast. Much faster than the gamma-function (factorial), for instance. Where did you encounter such a beast?

EDIT:
I should point out in case it isn't obvious, the above expansion is equivalent to
$<math>\log f_n = \sum_{k=1}^{n-1} \log(1+f_k)</math>$

EDIT2: and I should point out there that if you insert a suitable series expansion of the logarithm, you may end up with something you can use, assuming certain details about series convergence. Beware that the familiar form of the logarithm expansion for $<math>\log (1+x)</math>$ does not apply because it does not converge for $<math>x>1</math>$ .

Anomie

Member #9,403

January 2008

Quote:

Minor difference, but anyway.

Is there some distinction? Or is it bad to label something as a function if its results form a predictable series or something like that?

Quote:

It's a tricky little bugger. The closest I could come was ...

I hope you were having a good time. I think you've officially put much more effort into figuring this out than me. Then again, I have no idea what I'm doing, and I'm trying to figure it out with nothing but the help of Wikipedia and Google.

Quote:

Aside, this sequence grows astoundingly fast. Much faster than the gamma-function (factorial), for instance. Where did you encounter such a beast?

You really don't want to know.

______________
I am the Lorax. I speak for the trees. I speak for the trees for the trees have no tongues.

StevenVI

Member #562

July 2000

Quote:

You really don't want to know.

Code for "it's a homework assignment and I've been skipping class for a while."

__________________________________________________
_{Skoobalon Software}
_{[ Lander! v2.5 ] [ Zonic the Hog v1.1 ] [ Raid 2 v1.0 ]}

Evert

Member #794

November 2000

Quote:

Is there some distinction?

Yes, although as I said, it's subtle. The reason it's probably relevant has to do with search terms you may want to look for.

Quote:

I hope you were having a good time.

The alternative was watching my contact binary struggle through reverse mass transfer, which it's doing very very slowly.

Quote:

I think you've officially put much more effort into figuring this out than me.

Really? The above post took me maybe a few minutes, nothing major.

Anomie

Member #9,403

January 2008

Quote:

Code for "it's a homework assignment and I've been skipping class for a while."

Nope! I've taken all of the math courses that my school offers. I don't get to take any more until college, but I've been picking up random books at the local library.

Quote:

Really? The above post took me maybe a few minutes, nothing major.

Okay...then maybe 'effort' was the wrong word. You've been much more productive!

______________
I am the Lorax. I speak for the trees. I speak for the trees for the trees have no tongues.

Edgar Reynaldo

Major Reynaldo

May 2007

I don't really know how to figure this one out into a closed form equation, but it does have some interesting properties :

f(k)                   f'(k)               ~f''(k)              f'''(k)          ~f''''(k)
-------------------------------------------------------------------------------
f(0) = 1
                         +1
f(1) = 1 + 1                                *4        (2^2)
                         +4                                     +1      (1^2)
f(2) = 2 + 4                                *9        (3^2)                      *4
                         +36                                    +4      (2^2)
f(3) = 6 + 36                               *49       (7^2)                      *9
                         +1764                                  +36     (6^2)
f(4) = 42 + 1764                            *1849     (43^2)                     *49
                         +3261636                               +1764   (42^2)
f(5) = 1806 + 3261636                       *3265249  (1807^2)                   *1849
                         +10650053687364
f(6) = 3263442 + 10650053687364

I used ~f''(k) in the table as meaning psuedo second derivative, as the first rate of change doesn't change by addition, but multiplication. And that rate changes by addition of squares of a numerical sequence. As you descend into the further rates of change, they repeat in an alternating fashion, which is interesting.

Really, the only way I would know how to describe it is as a product series like Evert did.

f(0)  = 1
f(1)  = 1*2
f(2)  = 1*2*3
f(3)  = 1*2*3*7
f(4)  = 1*2*3*7*43
f(5)  = 1*2*3*7*43*1807
f(6)  = 1*2*3*7*43*1807*3263442

And yeah, that gets pretty massive pretty quickly.

Eagle and Allegro 5 binaries | Older Allegro 4 and 5 binaries | Allegro 5 compile guide
King Piccolo will make it so Then I could just flip it with some sweet, sweet matrix math. In either case, I’ll ride this wagon until the wheels fall off. Thanks to those that keep it running

SiegeLord

Member #7,827

October 2006

Quote:

nothing but the help of Wikipedia and Google

Your Google-fu is unfortunate. This sequence of yours is just one subtracted from the Sylvester's sequence, which has no known closed form solution. The wikipedia page suggests a formula that is the double-exponential of a constant, which unfortunately is not any easier to find than the sequence numbers themselves.

EDIT: A marginally better attempt is made here.

$<math>f(n) = \left\lfloor E^{2^{n+1}}+\frac12 \right\rfloor - 1</math>$

$<math>E=1.2640847353...</math>$

"For in much wisdom is much grief: and he that increases knowledge increases sorrow."-Ecclesiastes 1:18
[SiegeLord's Abode][Codes]:[DAllegro5]:[RustAllegro]

decepto

Member #7,102

April 2006

Nice find SiegeLord. I was pulling my hair out trying to find a closed solution to this.

--------------------------------------------------
Boom!

Anomie

Member #9,403

January 2008

Quote:

but it does have some interesting properties [...] As you descend into the further rates of change, they repeat in an alternating fashion, which is interesting.

That's cool!

Quote:

has no known closed form solution

Well crap.

It's not really vital for me to know this, I just thought it would be neat.

______________
I am the Lorax. I speak for the trees. I speak for the trees for the trees have no tongues.