wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Ladder Rungs answer
        
(Message started by: Drake on Aug 8^th, 2002, 1:59pm)

Title: Ladder Rungs answer
Post by Drake on Aug 8^th, 2002, 1:59pm

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+8) 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? 8)

Title: Re: Ladder Rungs answer
Post by AlexH on Aug 10^th, 2002, 1:42am

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].

Title: Re: Ladder Rungs answer
Post by rugga on Sep 3^rd, 2002, 8:43pm

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.

Title: Re: Ladder Rungs answer
Post by Icarus on Oct 20^th, 2002, 9:15pm

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 x_n = SUM A_ix_n-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 rⁿ for some r. Plugging x_n = rⁿ into the equation above and dividing by r^n-k gives the polynomial equation

r^k - A₁r^k-1 - ... -A_k = 0

Any root of the equation forms a sequence in the set, and if a particular root r has multiplicity m, then x_n = nⁱrⁿ for i < m are also sequences in the set.

This provides a complete basis for representing all sequences. Label the basis sequences {x_in} for i = 1 to k. To find the expression for a particular {y_n} (which is determined using the recursion from its first k values), set

y_n = SUM_i B_ix_in
and plug in the actual numbers for n = 1 to k, to get k equations in the k unknowns B_i. Solving gives you a closed form expression for {y_n}.

This can be applied to any of the k-step Fibonacci sequences.

Title: Re: Ladder Rungs answer
Post by rugga on Nov 9^th, 2002, 3:05am

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.

Title: Re: Ladder Rungs answer
Post by Icarus on Nov 11^th, 2002, 7:22pm

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.