From recursive to explicit?

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

DivideByZero
Posts: 56
Joined: Sun Oct 19, 2008 4:04 pm UTC

From recursive to explicit?

Postby DivideByZero » Tue Jul 07, 2009 3:17 pm UTC

I have a recursive formula:

b_n = 3^(b_n-1 - 1)

How would I express this explicitly?
I'm think its possible but I'm not sure how to do it.

Thanks in advance!

User avatar
MartianInvader
Posts: 782
Joined: Sat Oct 27, 2007 5:51 pm UTC

Re: From recursive to explicit?

Postby MartianInvader » Tue Jul 07, 2009 3:32 pm UTC

Well, it'll depend on your first term. If it's 1, for example, your sequence is pretty boring.
Let's have a fervent argument, mostly over semantics, where we all claim the burden of proof is on the other side!

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: From recursive to explicit?

Postby skeptical scientist » Tue Jul 07, 2009 5:06 pm UTC

That sequence looks like it can't be elementary, because it's faster growing than any elementary function. (Except in special cases like when it's always 1.) So I don't think there is a nice closed-form solution.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

DivideByZero
Posts: 56
Joined: Sun Oct 19, 2008 4:04 pm UTC

Re: From recursive to explicit?

Postby DivideByZero » Wed Jul 08, 2009 1:45 pm UTC

lets say the first term is 3 and I want to find b_8.

How can I do this explicitly so I don't have to recursivly work it out?

User avatar
e^iπ+1=0
Much, much better than Gooder
Posts: 2065
Joined: Sun Feb 15, 2009 9:41 am UTC
Location: Lancaster

Re: From recursive to explicit?

Postby e^iπ+1=0 » Wed Jul 08, 2009 2:18 pm UTC

Well let's see what sequence that gives us.

b_1=3^1=3
b_2=3^2=9
b_3=3^8=6561
b_4=3^6560=8230589863111210357596673796337694919342278319311694339603206000070559419320288282803635754418539885919066625428034
127876279878883108899293640219865259974562639377556925189452547962215969109242904081001301652991642812190863757488809542687619
521149555091077566285260699648566997913331124935750012683419480278265324704709064506370022752058994567791470216652915912131179
781008338824413313755200770291122017484079151923804164743045513270690374568605873315465038870763718474232685399107776633885826
318337776308280033394143959649004772869645934391822005526543183584730674577514082495314661439506384196082122301661045769099129
696202042949647269663055873031056305227387753285002638309460321625291656479440763560995099953780402412487567278739610453616399
023629005961546332922944143234837595601897832605380700674361464139900876451577103542643344780887563016479601601849045235298898
392360352354448944966526296491666860400483983364177137479279611165885150978109929781633823287141532442389797778750281883498957
595883145866514560546862614637990698391035629831441657989128165461126890969633468745609968611854024637956913515176846344657641
309213895543788363949425099727704219650360786829092902664657118849536286504571694021572553319861748997959201156207500966096912
786365345150746748045862670481557267240482528172064414439108690967464719299114062906464047781432373225431109414260938796501124
243869291997775654899563459305584868404961677175271971493392372983350748100871923481520957095938091813451874643140888185097815
855547240261834590570324243272485377476090014510927881706560442597225466052517846087895220668894181562683652079116948166892799
408709801801042424134908577896777139153401278930879135880514822532358202558778548252783006271295931464373789833415422113378042
684704524253395000342090965255544762323691502050462533804539814165342272956986221385782145782363200315158022350305517462009739
378033357321470549770046377498141323823641131792933368552519825723390686549876232662466437058452822400184550499912050260045550
602856865897916675490563823577217000164393136913061366882873165871401539128696588812887805902619051328183139481136471472224218
495757168331941333361455862987536101539535647097997155726862989767857044497698572175083932744256831153747470654965083319524363
984804414976483500695379951004960906022919265992223880029915313687225285433958554741308836572625273780224870440932103387756203
009852590231346524745163512263571785009586913259165550005823124131028681760343301055045410250136397638769001026568034317588052
924444253288420947455060462115170063326253249775306282542126030257143131854795644554131517751559505121069331658632092163376707
006451515250366124576319586412301719395394682808987121009650531435946765331309941905485085341518629590809196737886352113435189
625958458635685474283505665755841522714007584095553600387889475107826541600166342039596399858689745490575489128682332108686685
428290263771574420481929338652087236062661303355816352146870133697373985760944519201797551547535706810691428423217228199287358
988321123067723175982098664777426384449556211638403569384651112240360284070600778878581456351168231660781326479363201

I don't really see any pattern, and I don't think there is one for the reason skeptical scientist said.
Last edited by e^iπ+1=0 on Thu Jul 09, 2009 4:21 pm UTC, edited 1 time in total.
poxic wrote:You, sir, have heroic hair.
poxic wrote:I note that the hair is not slowing down. It appears to have progressed from heroic to rocking.

(Avatar by Sungura)

DivideByZero
Posts: 56
Joined: Sun Oct 19, 2008 4:04 pm UTC

Re: From recursive to explicit?

Postby DivideByZero » Wed Jul 08, 2009 3:20 pm UTC

Isn't there a way to convert recursive to explicit

without writing down sample values ?

User avatar
Hackfleischkannibale
Posts: 171
Joined: Sun Aug 10, 2008 7:51 pm UTC
Location: not the moon... yet.

Re: From recursive to explicit?

Postby Hackfleischkannibale » Wed Jul 08, 2009 3:46 pm UTC

Not generally.
If this sentence makes no sense to you, why don't you just change a pig?

User avatar
jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5965
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: From recursive to explicit?

Postby jestingrabbit » Wed Jul 08, 2009 4:17 pm UTC

You might be able to write something with Knuth's up arrow notation,

http://en.wikipedia.org/wiki/Knuth%27s_ ... w_notation

but what's the point really? The sequence goes huge really quick, and even caculating, say, the tenth term when the initial is 3 is going to require more numbers than there are atoms in the universe, or something ridiculous like that.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

Buttons
Posts: 858
Joined: Wed May 02, 2007 3:27 pm UTC
Location: Somerville

Re: From recursive to explicit?

Postby Buttons » Wed Jul 08, 2009 4:53 pm UTC

In fact, just writing the fifth term out would require more atoms of ink than there are atoms in the universe. Likewise, of course, with writing the sixth term as three to some power.

achan1058
Posts: 1783
Joined: Sun Nov 30, 2008 9:50 pm UTC

Re: From recursive to explicit?

Postby achan1058 » Wed Jul 08, 2009 7:31 pm UTC

DivideByZero wrote:Isn't there a way to convert recursive to explicit

without writing down sample values ?
If it is something nice, you can try using generating functions, but something like the above, no.

Random832
Posts: 2525
Joined: Wed Oct 10, 2007 4:38 pm UTC

Re: From recursive to explicit?

Postby Random832 » Wed Jul 08, 2009 7:39 pm UTC

Buttons wrote:In fact, just writing the fifth term out would require more atoms of ink than there are atoms in the universe. Likewise, of course, with writing the sixth term as three to some power.

What if you have really small handwriting?

/suspects what you meant to say is, more digits than there are atoms in the universe

Buttons
Posts: 858
Joined: Wed May 02, 2007 3:27 pm UTC
Location: Somerville

Re: From recursive to explicit?

Postby Buttons » Wed Jul 08, 2009 8:35 pm UTC

Random832 wrote:What if you have really small handwriting?

Eh, I thought it was a reasonable assumption that each digit would use at least one atom of ink.

User avatar
t0rajir0u
Posts: 1178
Joined: Wed Apr 16, 2008 12:52 am UTC
Location: Cambridge, MA
Contact:

Re: From recursive to explicit?

Postby t0rajir0u » Wed Jul 08, 2009 10:04 pm UTC

People usually care about explicit formulae because they offer a faster algorithm to compute a number than running through the recursion. In practice, and especially for this problem, this isn't true; even if you were able to express the general term in terms of some obscure notation, that wouldn't help you actually calculate any values. The function simply grows too fast.

User avatar
MartianInvader
Posts: 782
Joined: Sat Oct 27, 2007 5:51 pm UTC

Re: From recursive to explicit?

Postby MartianInvader » Wed Jul 08, 2009 10:33 pm UTC

Random832 wrote:
Buttons wrote:In fact, just writing the fifth term out would require more atoms of ink than there are atoms in the universe. Likewise, of course, with writing the sixth term as three to some power.

What if you have really small handwriting?

/suspects what you meant to say is, more digits than there are atoms in the universe


:shock: Is your handwriting so small you can write a digit using less than an atom of ink? Holy crap, I bet your teachers were sorry they let you bring in a sheet of handwritten notes for the test! "On my note sheet, I'm putting all of my notes from the course, the textbook, several other textbooks from related courses, some novels in case I get finish early and get bored... heck, just to be safe, I'll put every book that's ever been published. Ever."
Let's have a fervent argument, mostly over semantics, where we all claim the burden of proof is on the other side!

keeperofdakeys
Posts: 658
Joined: Wed Oct 01, 2008 6:04 am UTC

Re: From recursive to explicit?

Postby keeperofdakeys » Thu Jul 09, 2009 1:40 am UTC

MartianInvader wrote:
Random832 wrote:
Buttons wrote:In fact, just writing the fifth term out would require more atoms of ink than there are atoms in the universe. Likewise, of course, with writing the sixth term as three to some power.

What if you have really small handwriting?

/suspects what you meant to say is, more digits than there are atoms in the universe


:shock: Is your handwriting so small you can write a digit using less than an atom of ink? Holy crap, I bet your teachers were sorry they let you bring in a sheet of handwritten notes for the test! "On my note sheet, I'm putting all of my notes from the course, the textbook, several other textbooks from related courses, some novels in case I get finish early and get bored... heck, just to be safe, I'll put every book that's ever been published. Ever."

less than an atom of ink...
ASCII in binary using protons and neutrons maybe?

achan1058
Posts: 1783
Joined: Sun Nov 30, 2008 9:50 pm UTC

Re: From recursive to explicit?

Postby achan1058 » Thu Jul 09, 2009 2:44 am UTC

MartianInvader wrote: :shock: Is your handwriting so small you can write a digit using less than an atom of ink? Holy crap, I bet your teachers were sorry they let you bring in a sheet of handwritten notes for the test! "On my note sheet, I'm putting all of my notes from the course, the textbook, several other textbooks from related courses, some novels in case I get finish early and get bored... heck, just to be safe, I'll put every book that's ever been published. Ever."
Of course, now comes the problem of being able to efficiently search for what you wrote......

Birk
Posts: 236
Joined: Tue May 19, 2009 5:08 pm UTC

Re: From recursive to explicit?

Postby Birk » Thu Jul 09, 2009 3:41 am UTC

maybe you just have 20/10^-35 vision

User avatar
z4lis
Posts: 767
Joined: Mon Mar 03, 2008 10:59 pm UTC

Re: From recursive to explicit?

Postby z4lis » Thu Jul 09, 2009 4:58 am UTC

I believe we're approaching the point where you have to worry about what wavelength of light you're using so you can distinguish between objects. Perhaps it's best to switch on your electron scanning eyes?
What they (mathematicians) define as interesting depends on their particular field of study; mathematical anaylsts find pain and extreme confusion interesting, whereas geometers are interested in beauty.

User avatar
Sir_Elderberry
Posts: 4206
Joined: Tue Dec 04, 2007 6:50 pm UTC
Location: Sector ZZ9 Plural Z Alpha
Contact:

Re: From recursive to explicit?

Postby Sir_Elderberry » Thu Jul 09, 2009 1:14 pm UTC

Luckily, my vision works with W and Z bosons. Not photons.
http://www.geekyhumanist.blogspot.com -- Science and the Concerned Voter
Belial wrote:You are the coolest guy that ever cooled.

I reiterate. Coolest. Guy.

Well. You heard him.

DivideByZero
Posts: 56
Joined: Sun Oct 19, 2008 4:04 pm UTC

Re: From recursive to explicit?

Postby DivideByZero » Thu Jul 09, 2009 3:27 pm UTC

So this recursive formula came from doing a hyperoperation from the left side to right.


like a(4)3 = a(3)a(3)a(3)a

the normal approach is { a(3) { a(3) { a(3)a } } }
(which is the right to left computation)

I'm using the left to right computation and to find b_(n-1) i have to find b_(n-2) etc..
a(n)b = a * b_(n-1)


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 8 guests