Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm not sure if this problem is linear or not. Anyway, let me state the problem first:

$$ \begin{align} P_n(a) &= \left(1 - \frac{a}{n} \times \frac{a-1}{n-1}\right) \times P_{n-1}(a) + \left(\frac{a}{n} \times \frac{a-1}{n-1}\right) \times P_{n-1}(a-2) \\ &where \space 0 \le a \le n, a \space and \space n \space are \space integers; \\ \\ P_n(a) &= 0 \\ &othertwise. \end{align} $$ provided that $$ P_1(0) = 0, \\ P_1(1) = 1, $$ and $$ P_2(0) = 0, \\ P_2(1) = 1, \\ P_2(0) = 0. $$

(I don't know whether $P_2$ would be necessary, but I provide them here in case they are.)

I have already read several answers (such as Solving recurrence relation in 2 variables, Solving a recurrence relation in 2 variables, and A recurrence relation on two variables), but it seems that they don't fit my problem at all.

In particular, answer in "A recurrence relation on two variables" requires me to "observe a pattern", which I can't for this problem.

Any hints would be appreciated. Thanks in advance!

share|cite|improve this question

At first glance it seems like separation of variables might work. That is, suppose that there exists sequences, $f_n$ and $g_a$ such that $P_{n,a} = f_n g_a$ then,

$$f_n g_a = (1 - \frac{a(a-1)}{n(n-1)})f_{n-1}g_a + \frac{a(a-1)}{n(n-1)}f_{n-1}g_{a-2} $$

now multiply both sides by $n(n-1)$, divide both sides by $f_{n-1} g_a$, and proceed to completely separate the variables n and a: $$ n(n-1)\frac{f_n}{f_{n-1}} = n(n-1) - a(a-1) + a(a-1)\frac{g_{a-2}}{g_a} \\ n(n-1)(\frac{f_n}{f_{n-1}} - 1) = a(a-1)(\frac{g_{a-2}}{g_a} - 1) $$

Introduce a fixed constant $b$, set both sides equal to it, and then solve for f and g:

$$ b = n(n-1)(\frac{f_n}{f_{n-1}} - 1) = a(a-1)(\frac{g_{a-2}}{g_a} - 1) \\ f_n = (1+\frac{b}{n(n-1)})f_{n-1} = \prod_{j=2}^n[1+\frac{b}{j(j-1)}]f_1 \\ g_a = \frac{g_{a-2}}{1+\frac{b}{a(a-1)}} = \prod_{j=0}^{\lfloor {a/2} \rfloor -1}[\frac{1}{1+\frac{b}{(a-2j)(a-1-2j)}}]g_{a-2\lfloor {a/2} \rfloor}$$

Notice that $a-2\lfloor {a/2} \rfloor$ is the remainder when $a$ is divided by $2$ and so will be $0$ if $a$ is even and $1$ if $a$ is odd. Now your initial conditions imply that:

$f_1 g_0 = 0 \land (1+\frac{b}{2})f_1 g_0 = 0 \land (1+\frac{b}{2})f_1 g_1 = 1$

So this means that $f_1 \neq 0 \land b \neq -2 \land g_0 = 0 $.

Now this solution neglects the conditions that the function is zero whenever $a$ is less than 0 or greater than $n$, or a or n are not integers. To take care of those conditions it would probably be easiest to use an indicator function. Also, if you need more flexibility in your solution you can take your solution to be a linear combination of some collection of functions of the form:

$$\prod_{j=2}^n[1+\frac{b_t}{j(j-1)}] \prod_{j=0}^{\lfloor {a/2} \rfloor -1}[\frac{1}{1+\frac{b_t}{(a-2j)(a-1-2j)}}]G_{t,a-2\lfloor {a/2} \rfloor} $$

where for each $t$, $b_t$ is a fixed constant and $G_{t, \bullet}$ is a function on $\lbrace 0,1 \rbrace$

share|cite|improve this answer
Thanks! Your answer is very intuitive! – Siu Ching Pong -Asuka Kenji- Jan 25 '15 at 14:14

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.