Number sequence help

Shakti · 05-26-2005, 07:14 AM

Say I have the following recursive numbersequence: a(n) = a(n-1)+2a(n-2)

I know that a(1) = 2 and I know that a(2) = 3. Now I need to find an explicit formula for that.

I know it has something to do with fibonaccis sequence since, if a(1)=1 and a(2) = 1 the explicit formula would have been a(n) = (2^n-(-1)^n)/3. The problem that this does not work when a(1) = 2 and a(2) = 3.

Can anybody explain how I should come up with an explicit formula for this problem?

ober · 05-26-2005, 07:15 AM

The answer..... is 42.

Shakti · 05-26-2005, 07:15 AM

herrrrrrrrrrrm.......ummmmmmmmm.......no

Sang-drax · 05-26-2005, 07:35 AM

It can be solved with matrices. I'll see if I can produce some images for you.

Shakti · 05-26-2005, 07:38 AM

That would be very nice!!

Sang-drax · 05-26-2005, 08:30 AM

OK, the board is semi-down right now, so we'll see if this gets through..

I'm going to assume that you know how to handle matrices. First, we'll define a matrix A like this:

Sang-drax · 05-26-2005, 08:31 AM

Ahh, the boards are back!

Now, we add your recursive formula:

Shakti · 05-26-2005, 08:31 AM

Ok....yah I know how to handle matrices (at least to the point where I can multiply them).

Sang-drax · 05-26-2005, 08:32 AM

We want to diagonalize X, to make it easy to calculate X^n.

Sang-drax · 05-26-2005, 08:34 AM

When we perform the last multiplication with A2, the first row of the result will be a(n+2).

Here's the final formula:

Sang-drax · 05-26-2005, 08:36 AM

Numbers generated from this formula:

3 7 13 27 53 107 213 427 853 1707 3413 6827 13653 27307 54613 109227 218453 436907 873813 1747627 3495253

Seems correct for the first three, at least. HTH

Shakti · 05-26-2005, 08:36 AM

That definately seems to be correct! Thanks a bunch, now I just have to get a good grip on everything but that shouldnt be too hard...

! Thanks.

It is correct for the 18 first numbers.

05-26-2005, 07:14 AM	#1
Shakti Registered User Join Date: Aug 2003 Posts: 782	Number sequence help Say I have the following recursive numbersequence: a(n) = a(n-1)+2a(n-2) I know that a(1) = 2 and I know that a(2) = 3. Now I need to find an explicit formula for that. I know it has something to do with fibonaccis sequence since, if a(1)=1 and a(2) = 1 the explicit formula would have been a(n) = (2^n-(-1)^n)/3. The problem that this does not work when a(1) = 2 and a(2) = 3. Can anybody explain how I should come up with an explicit formula for this problem?
Shakti is offline

05-26-2005, 07:15 AM	#2
ober 5\|-\|1+\|-\|34\|) Join Date: Aug 2001 Posts: 4,429	The answer..... is 42.
ober is offline

05-26-2005, 07:15 AM	#3
Shakti Registered User Join Date: Aug 2003 Posts: 782	herrrrrrrrrrrm.......ummmmmmmmm.......no
Shakti is offline

05-26-2005, 07:35 AM	#4
Sang-drax and the hat of marbles Join Date: May 2002 Location: Lund, Sweden Posts: 2,041	It can be solved with matrices. I'll see if I can produce some images for you. __________________ Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling
Sang-drax is offline

05-26-2005, 07:38 AM	#5
Shakti Registered User Join Date: Aug 2003 Posts: 782	That would be very nice!!
Shakti is offline

05-26-2005, 08:30 AM	#6
Sang-drax and the hat of marbles Join Date: May 2002 Location: Lund, Sweden Posts: 2,041	OK, the board is semi-down right now, so we'll see if this gets through.. I'm going to assume that you know how to handle matrices. First, we'll define a matrix A like this: Attached Images __________________ Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling
Sang-drax is offline

05-26-2005, 08:31 AM	#7
Sang-drax and the hat of marbles Join Date: May 2002 Location: Lund, Sweden Posts: 2,041	Ahh, the boards are back! Now, we add your recursive formula: Attached Images __________________ Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling
Sang-drax is offline

05-26-2005, 08:32 AM	#9
Sang-drax and the hat of marbles Join Date: May 2002 Location: Lund, Sweden Posts: 2,041	We want to diagonalize X, to make it easy to calculate X^n. Attached Images __________________ Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling
Sang-drax is offline

05-26-2005, 08:34 AM	#10
Sang-drax and the hat of marbles Join Date: May 2002 Location: Lund, Sweden Posts: 2,041	When we perform the last multiplication with A2, the first row of the result will be a(n+2). Here's the final formula: Attached Images __________________ Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling
Sang-drax is offline

05-26-2005, 08:36 AM	#11
Sang-drax and the hat of marbles Join Date: May 2002 Location: Lund, Sweden Posts: 2,041	Numbers generated from this formula: 3 7 13 27 53 107 213 427 853 1707 3413 6827 13653 27307 54613 109227 218453 436907 873813 1747627 3495253 Seems correct for the first three, at least. HTH __________________ Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling
Sang-drax is offline

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
scanf oddities	robwhit	C Programming	5	09-22-2007 01:03 AM
number sequence	valleyboy	C Programming	1	05-01-2005 02:24 PM
Prime number program problem	Guti14	C Programming	11	08-06-2004 04:25 AM
parsing a number	juancardenas	C Programming	1	02-19-2003 01:10 PM
Random Number problem in number guessing game...	-leech-	Windows Programming	8	01-15-2002 05:00 PM