Author |
Topic: Ladder Rungs answer (Read 4004 times) |
|
Drake
Newbie
Gender: 
Posts: 7
|
 |
Ladder Rungs answer
« on: Aug 8th, 2002, 1:59pm » |
 Quote  Modify
|
Forgive me if this answer ends up being kinda long, I'm trying to reason it out as I type. I think the formula for this is that for n rungs, you add the number of combinations for the previous K values of n.
For the case stated with 2 options (K=2) for each movement, and starting with 1 rung, you obviously have 1 possibility.
With 2 rungs you have 2 possibilities: 0-1-2, or 0-2
Going up one to 3 rungs you have 3 possibilities:
0-1-2-3, 0-2-3, 0-1-3
At 4 rungs you have 5 possibilities:
0-1-2-3-4, 0-2-3-4, 0-1-3-4, 0-1-2-4, 0-2-4
And it continues on.. Each time you add a rung, you can then get to that rung directly from the previous 2 rungs, so you need to add those 2 together.
ie, for 5 rungs you can get to rung 5 directly from rung 3 or rung 4 so you add the combinations of those 2 together for a total of 8 possibilities.
For 6 rungs, you add the totals for 4 and 5 rungs (5+ for a total of 13 possibilities.
In the cases where K > 2, you would be able to get to run n directly from any of the previous K rungs, and thus would add those combinations together.
Right?
|
| « Last Edit: Aug 8th, 2002, 2:15pm by Drake » |
 IP Logged |
|
|
|
AlexH
Full Member
Posts: 156
|
|
Re: Ladder Rungs answer
« Reply #1 on: Aug 10th, 2002, 1:42am » |
Quote Modify
|
Correct Drake. This is called the Fibonacci sequence. You can compute the terms of it directly if you want. If Phi = (1+ sqrt(5))/2, then Fib(n)= (Phi^n - (-Phi)^(-n))/sqrt[5].
|
|
IP Logged |
|
|
|
rugga
Newbie
Gender:
Posts: 21
|
|
Re: Ladder Rungs answer
« Reply #2 on: Sep 3rd, 2002, 8:43pm » |
Quote Modify
|
Nice answers, guys. Just to round it out, Drake's
solution for the general case (k>2) corresponds to
the Fibonacci n-step numbers. I don't think there
is a single closed-form formula for all n and k, but
there are for some specific values of k, such as
AlexH's formula for k=2.
There's some info about n-step Fibonacci's at
http://mathworld.wolfram.com/Fibonaccin-StepNumber.html. Also follow the links for
Tribonacci (k=3) and Tetranacci (k=4) numbers.
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Ladder Rungs answer
« Reply #3 on: Oct 20th, 2002, 9:15pm » |
Quote Modify
|
Rugga: There is a general method for generating closed form expressions for sequences satisfying a linear recursion formula with constant coefficients (Whew! That was a mess to say!)
Let me know if I am wrong, but from your various posts I believe your math background is more than sufficient to follow this.
Consider all sequences satisfying xn = SUM Aixn-i for i = 1 to k.
The set of these sequences forms a vector space of dimension k. So we only need to find k independent sequences to express all possible ones. The ones we want are of form rn for some r. Plugging xn = rn into the equation above and dividing by rn-k gives the polynomial equation
rk - A1rk-1 - ... -Ak = 0
Any root of the equation forms a sequence in the set, and if a particular root r has multiplicity m, then xn = nirn for i < m are also sequences in the set.
This provides a complete basis for representing all sequences. Label the basis sequences {xin} for i = 1 to k. To find the expression for a particular {yn} (which is determined using the recursion from its first k values), set
yn = SUMi Bixin
and plug in the actual numbers for n = 1 to k, to get k equations in the k unknowns Bi. Solving gives you a closed form expression for {yn}.
This can be applied to any of the k-step Fibonacci sequences.
|
| « Last Edit: Oct 31st, 2002, 8:55pm by Icarus » |
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
rugga
Newbie
Gender:
Posts: 21
|
|
Re: Ladder Rungs answer
« Reply #4 on: Nov 9th, 2002, 3:05am » |
Quote Modify
|
Thank you Icarus!
That's really beautiful and I've never seen it before. It took me a couple days to grok it but now I feel like I've really learned something and gained a new tool. Thanks.
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Ladder Rungs answer
« Reply #5 on: Nov 11th, 2002, 7:22pm » |
Quote Modify
|
You're welcome. I've always been fond of this one. Of course, for recursions of order greater than 2, and particularly greater than 4, it can be difficult to find the roots. But the usefulness of the these closed form expressions is in what they tell us about the overall behavior of the sequences rather than in calculating actual values.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print