1

We are provided with a recurrence relation as follows:-

$F(n,k) = F(n,k-1) + F(n-k+1,k)$
$F(n,1) = n $
$F(X,k) = 0$ if $ (X\leq0)$

I need help in solving this for k=1 to 10 only
Edit:- I have added values I computed using a simple program upto n=25 and k=25( i wanted a general way for all k , but question demands only for k=1 to 10) .

enter image description here

user249117
  • 245
  • The first thing to do when faced with a problem like this, especially if you don't know how to get started solving it, is to compute a portion of the table of values, to get a "feel" for the numbers. Have you done this? – Barry Cipra Dec 09 '15 at 14:44
  • yes i have computed it , for n from 1 to 25 . I observed a pattern , and as soon as i feel i have got the idea , after some interval , the idea proves to be wrong. – user249117 Dec 09 '15 at 14:51
  • It would help if you edited your question to include a (small) portion of what you've computed. (For one thing, it's possible you computed something incorrectly, in which case people can use that as a starting point.) In general, you'll get more and better answers if people can see what you've tried and where you're stuck. – Barry Cipra Dec 09 '15 at 15:15
  • @BarryCipra added now – user249117 Dec 09 '15 at 15:41
  • Excellent! The next thing to do, when you've computed some entries of a table, is to take some of the rows or columns (or diagonals) to the OEIS -- http://oeis.org -- and see if it recognizes any of them. Oftentimes you can find the solution to your problem there. In this case, however, I myself am stumped. The OEIS does recognize various of the columns, as well as the main diagonal ($1,3,7,14,26,45,\ldots$), but not in a way that I can see a simple consistent pattern. Which makes me ask, what do you mean by "solving" a recurrence relation? (cont.) – Barry Cipra Dec 09 '15 at 17:34
  • I.e., if this is a homework problem, exactly what kind of answer is it looking for? – Barry Cipra Dec 09 '15 at 17:34
  • The question is part of some software project , which demands k=1 to 10 only . I was interested in solving it for all K. Therefore , initially i didn't mention this point. – user249117 Dec 09 '15 at 18:13

1 Answers1

1

I have an estimate, based on the well-known $\sum_{m=k}^n{m\choose k}={n+1\choose k+1}$. My estimate is for when $n$ is much bigger than $k$.
$$F(n,2)=F(n,1)+F(n-1,2)=F(n,1)+F(n-1,1)+F(n-2,1)+...={n+1\choose2}\\ F(n,3)=F(n,2)+F(n-2,2)+F(n-4,2)+...\approx\frac12{n+2\choose3}\\ F(n,4)\approx\frac1{3!}{n+3\choose4}$$ The fractions come because only half the F(m,2) and a third of the F(m,3) contribute to the sum. So my estimate when $n\gg k$ is $$F(n,k)\approx\frac1{(k-1)!}{n+k-1\choose k}$$
Of course, when $k>n$, then $F(n,k)=F(n,n)$

Empy2
  • 50,853