Competition - post a photo you've taken of nature >>

Recursive sequence question

I'm really stuck on this problem. I've found the answer but I'm not sure I've done it the right way. I don't really know what recursive means. If it's finding a formula for one term to the next then I can't do it. The question is:

I've got:

[br]g(23)=g(70)+1=g(35)+2=g(106)+3=g(53)+4=g(160)+5=g(40)+7=g(13)+6=g(4)+5=8

Thanks for any help!

Reply 1

ghostwalker

Original post by jamie092

...

See Recursion The factorial definition there is the classic example of recursion.

I think you've gone wrong in your example in going from g(40)+7 to g(13)+6.

Edit: Aside from the "+1" bit this relates to the Collatz or 3+1 conjecture

(edited 11 years ago)

Reply 2

jamie092

I just used g(3n+1)=g(n)-1 for that step, I can't see how that's wrong (I'm not saying it's not wrong, just that I'm not feeling very awake ^^)

Yeah I looked at that wikipedia page but I didn't really get anywhere because all other examples of recursive sequences define the nth term in terms of the (n-1)th term.

That Collatz conjecture does look interesting though, I've bookmarked it! :P

Reply 3

ghostwalker

Original post by jamie092

I just used g(3n+1)=g(n)-1 for that step, I can't see how that's wrong (I'm not saying it's not wrong, just that I'm not feeling very awake ^^)

That's not something you can validly do.

If we paraphrase the definition of g(n) for n odd, it says:

g(n) is defined to be g(3n+1) + 1.

From this you cannot infer g(3n+1) is defined to be g(n) - 1

The "=" sign is perhaps misleading in this context.

Yeah I looked at that wikipedia page but I didn't really get anywhere because all other examples of recursive sequences define the nth term in terms of the (n-1)th term.

That's the basic form of recursion, the nth term is defined in terms of the (n-1)th. There is a computer algorithm further down that shows it nicely.

(edited 11 years ago)

Reply 4

jamie092

Original post by ghostwalker

That's not something you can validly do.

If we paraphrase the definition of g(n) for n odd, it says:

g(n) is defined to be g(3n+1) - 1.

From this you cannot infer g(3n+1) is defined to be g(n) + 1

The "=" sign is perhaps misleading in this context.

Reply 5

ghostwalker

Original post by jamie092

But if I have to use the definition that way around, then I can only calculate g(23) from terms above it i.e g(23)=g(70) +1 and then I'd have to keep going, the only way to get in terms of lower terms would be to use that g(even)=g(even/2).

That's prefectly correct.

You started at g(23) and after several steps got to g(40), which leads you to g(20), to g(10), to g(5), and then up to g(16)....

The process goes up and down, until you get to 1 - at least according to the Collatz Conjecture.

Reply 6

jamie092

Original post by ghostwalker

That's prefectly correct.

You started at g(23) and after several steps got to g(40), which leads you to g(20), to g(10), to g(5), and then up to g(16)....

The process goes up and down, until you get to 1 - at least according to the Collatz Conjecture.

Ah ok then, well thanks a lot!

I got that g(2^n)=n+1 from the even part which is kind of nice. And then numbers such that n=2^m where n=3k+1 are going to be useful.

I was just wondering if that's the only way to do it, number by number, or if I can calculate a formula like T_n=f(n) or something

(edited 11 years ago)

Reply 7

ghostwalker

Original post by jamie092

A lot of work has gone into investigating the Collatz Conjecture, and as it stands, it's still a conjecture.

If you can find a formula, you'll be due an honourary Ph.D. at least, I think.

Reply 8

jamie092

Original post by ghostwalker

A lot of work has gone into investigating the Collatz Conjecture, and as it stands, it's still a conjecture.

If you can find a formula, you'll be due an honourary Ph.D. at least, I think.