Solution to this recurrence?

Question

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.

Answer 1

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}. $$