3

Is there exists a solution to this recurrence. $$F(N,1) = N, N≥1$$

$$F(N,K) = \frac {1}{\lfloor\frac 1{F(N-1,K-1)} -\frac 1{F(N,K-1)}\rfloor} \;\;\;\;2≤K≤N$$

I tried to simplify the equation but i am not able to find F(1,2) and thus unable to proceed. I am new to this site,so please let me know if i have not asked the question properly.

lulu
  • 70,402
Simpi
  • 59
  • Note: I reformatted your formula. Please check to make sure I didn't accidentally change your meaning. – lulu Oct 08 '15 at 18:07
  • 1
    just to confirm: To compute $F(1,2)$ we note that $F(0,1)=0$ and $F(1,1)=1$. Thus the denominator of your expression would be undefined since it contains a term which resolves to $\frac 10$, Or have I misunderstood? – lulu Oct 08 '15 at 18:12
  • Yes,you have misunderstood it..We can't calculate F(1,2) this way...I was also stucked there. – Simpi Oct 08 '15 at 18:48

1 Answers1

3

The original recurrence relation is equivalent to $$ \frac{1}{F(N,K)} = \frac{1}{F(N-1,K-1)} - \frac{1}{F(N,K-1)}. $$

For $K = 2$, we have \begin{align} \frac{1}{F(N,2)} &= \frac{1}{F(N-1,1)} - \frac{1}{F(N,1)} \\ &= \frac{1}{N-1} - \frac{1}{N} \\ &= \frac{1}{N\,(N-1)}. \end{align}

Next, for $K = 3$, we have \begin{align} \frac{1}{F(N,3)} &= \frac{1}{F(N-1,2)} - \frac{1}{F(N,2)} \\ &= \frac{1}{(N-1) \, (N-2)} - \frac{1}{N \, (N-1)} \\ &= \frac{N}{N \, (N-1) \, (N-2)} - \frac{N-2}{N \, (N-1) \, (N-2)} \\ &= \frac{2}{N\,(N-1)\,(N-2)}. \end{align}

So we can guess,

(1) \begin{align} \frac{1}{F(N,K)} &= \frac{(K-1)!}{N\,(N-1)\,(N-2)\,(N-K+1)}. \end{align}

Let us prove it by induction, suppose (1) holds for $K = k$, For $K = k+1$, \begin{align} \frac{1}{F(N,k+1)} &= \frac{1}{F(N-1,k)} - \frac{1}{F(N,k)} \\ &= \frac{(k-1)!}{(N-1) \, (N-2) \, (N-k)} - \frac{(k-1)!}{N \, (N-1) \, (N-k+1)} \\ &= \frac{(k-1)! \, N }{ N \, (N-1) \, (N-2) \dots (N-k)} - \frac{(k-1)! \, (N-k)}{N \, (N-1) \, (N-k+1)\dots (N-k)} \\ &= \frac{k!}{N\,(N-1)\,(N-2)\,(N-k)}, \end{align} which means (1) also holds for $K = k+1$.

So $$ F(N,K) = \frac{N(N-1)\dots(N-K+1)}{(K-1)!} = N \, {N-1 \choose K-1}. $$

hbp
  • 157