Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!think.com!zaphod.mps.ohio-state.edu!wuarchive!uunet!munnari.oz.au!manuel!csc.anu.edu.au!bdm659
From: bdm659@csc.anu.edu.au
Newsgroups: comp.theory
Subject: Re: Closed form solution to a recurrence
Message-ID: <1991May24.105457.1@csc.anu.edu.au>
Date: 23 May 91 23:54:57 GMT
References: <9105231143.AA25697@dali.uni-paderborn.de>
Sender: news@newshost.anu.edu.au
Organization: Computer Services, Australian National University
Lines: 26

In article <9105231143.AA25697@dali.uni-paderborn.de>, atze@UNI-PADERBORN.DE (Ralf Klasing) writes:
> I'm desperately looking for a closed formula of the
> following recurrence relation
>
>   A(0,0) = 1
>   A(0,i) = 0  for all i <> 0
>   A(1,0) = A(1,1) = 1
>   A(1,i) = 0 for all i <> 0,1
>
>   A(i,k) = A(i-1,k) + A(i-2,k-1) for all i >= 2

If C(n,k) denotes the binomial coefficients, taken to be 0 except
where 0 <= k <= n, then   A(i,k) = C(i-k,k-1) + C(i-k,k).

Derivation: The number of paths from (0,0) to (x,y) using steps of size
(1,0) and (2,1) is C(x-y,y) as you can see by noting that there must be y
steps of the second kind and x-y steps altogether.  Now think of your
problem geometrically.  A(i,k) is the number of paths starting at one
of the points in S = {(0,0),(1,0),(1,1)} and finishing at the point
(i,k), with the restriction that only the first point of the path lies
in S.  The latter restriction can be dropped if point (1,0) is also
dropped, as paths beginning (0,0)-(1,0)-... cover those which start at
(1,0).  Hence we have the total number of paths from (0,0) to (i,k), which
is C(i-k,k) plus the total number from (1,1) to (i,k), which is C(i-k,k-1).

Brendan.