Serving the Quantitative Finance Community

 
User avatar
iwanttobelieve
Topic Author
Posts: 1
Joined: August 20th, 2006, 7:09 am

Usefull functional equation

November 7th, 2006, 8:53 am

Hi folks,I post here a usefull equation, for a GS interview for example.Suppose you have a function f, defined on NxN, that verifies:(1) f(n,k) = f(n-1,k) + f(n, k-1)(2) together with some relevant initial condition.--> Solve {(1),(2)}, that is express f with some known functionals.Hint: a. The easiest way to prove that is to know the answer (or have an intuition) as f is uniquely determined by induction.
Last edited by iwanttobelieve on November 6th, 2006, 11:00 pm, edited 1 time in total.
 
User avatar
souaf
Posts: 0
Joined: January 7th, 2003, 4:37 pm

Usefull functional equation

November 7th, 2006, 1:24 pm

Hi thereI find : f(n,m) = sum (i=1 to n ) ( C(n+m-i-1 , n-i ) * xi ) + sum(j=1 to m ) ( C(n+m-1-j , n-1) * yj )where : xi = f(i,0) and yj = f(0,j)
 
User avatar
iwanttobelieve
Topic Author
Posts: 1
Joined: August 20th, 2006, 7:09 am

Usefull functional equation

November 7th, 2006, 8:51 pm

Ok, you now have gained access to the everyday life application. Suppose you have a n times m grid and that you want to travel from bottom left corner to up right corner, only going up or right. How many paths can you take ?
Last edited by iwanttobelieve on November 6th, 2006, 11:00 pm, edited 1 time in total.
 
User avatar
sevvost

Usefull functional equation

November 7th, 2006, 9:18 pm

This simple question does not require recurrent equations - or any other calculations, for that matter. What is your point?
 
User avatar
iwanttobelieve
Topic Author
Posts: 1
Joined: August 20th, 2006, 7:09 am

Usefull functional equation

November 7th, 2006, 9:55 pm

QuoteOriginally posted by: sevvostThis simple question does not require recurrent equations - or any other calculations, for that matter. What is your point?You mean you have a probabilistic argument to solve it directly ? Well the point is that if you denote by f(n,k) such a number then f(n,k) can be decomposed in paths that go up at 1st step which is f(n-1,k) and paths that do right, f(n, k-1). There surely exists a way of counting directly the paths, I have to think about it, but if you already have one, I am interested in it. Edit:Ah, I may see.. the length of the path is n+k and you choose n point among them to turn right... the idea is to put this problem in bijection with a simpler problem. You're right. In very deed. Edit:Ok, clash , yes combinatorial or probabilistic means the same to me, my dictionnary doesn't translate the french 'dénombrement' correctly :/
Last edited by iwanttobelieve on November 6th, 2006, 11:00 pm, edited 1 time in total.
 
User avatar
sevvost

Usefull functional equation

November 7th, 2006, 10:04 pm

The argument is combinatorial, not probabilistic and a very straighforward one. A path consists of (m+n) legs of which, say, m go up. The number of paths is . Edit: crossed with your edit...
Last edited by sevvost on November 6th, 2006, 11:00 pm, edited 1 time in total.
 
User avatar
iwanttobelieve
Topic Author
Posts: 1
Joined: August 20th, 2006, 7:09 am

Usefull functional equation

September 19th, 2007, 8:47 pm

Now, I have a (n x p) grid and I want to go from bottom left corner to top right corner.I can move the following way:- one step right- one step up- one diagonal step (right + up)(I cannot go out of the grid).The question reads:"What is the total number of different paths."
 
User avatar
Advaita
Posts: 0
Joined: April 20th, 2005, 1:54 pm

Usefull functional equation

October 4th, 2007, 4:45 pm

Or If you align the grid nicely, you see it is actually a Pascal triangle