recurrence relation with 2 variables

Question

I need to solve the following reccurence relation: $$a(k,n)=\frac{(n-k)*a(k,n-1)+k*a(k-1,n)}{n}$$ with: $$a(0,n)=0, a(\frac{n}{2},n)=0$$ well im sure that $a(k,n)$ is 0 for every $k,n \in N$ but i dont know how to prove it. Thanks.

Answer 1

It can be proved using Induction on $k$ for values, $k=0,1,...n$.

Step 1: Base step $a(k,n) = 0$ for $k=0$, which is given as the boundary condition.

Step 2: Assume $a(k-1,n) = 0$ and we need to prove $a(k,n) = 0$.

$a(k,n) = \frac{(n-k)a(k,n-1) + ka(k-1,n)}{n} = \frac{(n-k)a(k,n-1)}{n} = \frac{(n-k)(n-k-1)a(k,n-2)}{n(n-1)} = ... = \frac{(n-k)(n-k-1)...(n-k-i+1)a(k,n-i)}{n(n-1)...(n-i+1)}$

Scenario 1: $k < \frac{n}{2}$

Now pick $i= n-2k > 0$ so that rightmost expression becomes a multiple of $a(k,2k)$ which is 0 according to the second boundary condition. Note that there exists a non-zero integer $i = n-2k$ under this scenario.

Scenario 2: $k = \frac{n}{2}$

In this scenario, $a(k,n) = a(\frac{n}{2},n) =0 $ as per the boundary condition.

Scenario 3: $k=n$

We can apply one-step recursion to $a(n,n)$ to see that it's 0.

Scenario 4: $n>k > \frac{n}{2}$

In this scenario, pick $i = n-k > 0$ so that rightmost expression becomes a multiple of $a(k,k)$ which is 0 from scenario 3. Similarly note that non-zero integer $i$ exists under this scenario.