I have the following recurrent relation and I want to find a close form of it if it exists at all.

$$ P_n = (1-p)^{n-1}P_{n-1} + \sum\limits_{k=2}^{n} \binom{n-1}{k-1} p^{\binom{k}{2}} (1-p)^{k(n-k)} P_{n-k} $$

Here $p$ is a constant in $[0;1]$, $P_0 =1$. It can be done with a little effort that $P_1 = 1$, $P_2 = p + 1 - p = 1$, $P_3 = 1 - 3p^2(1-p)$ and so on (it's getting messier after this step). I tried to write several first member and what I get is that $P_n = p^{\binom{n}{2}} + (1-p)^{\binom{n}{2}} + F(p)$ where $F(p)$ is a non-negative polynomial on $[0;1]$ with max power $\binom{n}{2}$.

So my questions are: 1) is it the linear recurrent relation for such that we usually build the characteristic polynomial and do the math like at school?

2) any known problems which involve such type of recursions (different size of sum for different $n$)?

3) any methodology how to approach it?

4) Maybe someone can solve it?

Thank you for your attention.


After substituion $t = n - k$ the recursion takes form $$ P_n = \sum\limits_{t=0}^{n-1} \binom{n-1}{t} p^{\binom{n-t}{2}} (1-p)^{t(n-t)} P_t $$,

which is similar to Bell number recurrence.

[edit 2]

Special case for $p=1/2$ as suggested by Pietro Majer takes the form $$ P_n(\frac{1}{2}) = 2^{-\binom{n}{2}}\sum_{t=0}^{n-1} \binom{n-1}{t} 2^{\binom{t}{2}} P_t(\frac{1}{2}) $$ and leads to Bell number.


Here is a generating function approach. Note that the RHS is almost a convolution $\sum_{k=0}^n a_{k}b_{n-k}$, which suggests the use of generating functions, after some bricolage on the the recursion aimed to get a convolution form (whence a Cauchy product of power series).

To start with, note that the first term on the RHS may be naturally included in the sum for $k=1$. The binomial has already a suitable form; and then note the exponent of $(1-p)$: it can be written $k(n-k)= {n \choose 2}-{ n-k\choose 2} -{k\choose2} $, which suggests to multiply the relation by $ (1-p)^{-{n\choose 2}}{x^{n-1}\over(n-1)!}$ : $$(1-p)^{-{n\choose 2}}P_{n}{x^{n-1}\over (n-1)!}= p^{k\choose 2 }(1-p)^{-{k\choose2}}{x^{k-1}\over(k-1)!}\cdot (1-p)^{-{n-k\choose 2}} P_{n-k}{x^{n-k}\over (n-k)!} $$

If we introduce the generating functions

$$g(x)=g(x,p):=\sum_{n=1}^\infty \Big({p\over 1-p}\Big)^{n \choose 2 }{x^{n}\over n!}$$ $$f(x)=f(x,p):=\sum_{n=0}^\infty (1-p)^{-{n\choose2}}P_{n}{x^{n}\over n!} $$ the recurrence relations write $f'=g'f$, whence $$f(x)=\exp\Big( \sum_{n=1}^\infty \Big({p\over 1-p}\Big)^{n \choose 2 }{x^{n}\over n!}\Big).$$

Incidentally, for $p=1/2$ one has $g(x)=e^x-1$, and we obtain the special values $$P_n(1/2)=2^{-{n\choose 2}}B_n$$ where $B_n$ are the Bell numbers.

Given that in the above formula for $f(x)$ the variable $p$ only enters in the term ${p\over 1-p}$, we may express the polynomials $P_n$ as $$P_n(p )=(1-p)^{n\choose 2}Q_n\big({p\over1-p}\big)$$ where the sequence $Q_n(q)$ is defined correspondingly by the somehow simpler generating series $$F(x)=F(x,q)=\sum_{n=0}^\infty Q_{n}{x^{n}\over n!} := \exp G(x,q)$$ where $$G(x)=G(x,q)=g\Big(x,{q\over q+1}\Big) := \sum_{n=1}^\infty q^{n \choose 2 }{x^{n}\over n!} $$ is the power series solution to the linear delay differential equation $$G(0)=0$$ $$G'(x)=1+G(qx).$$ The first polynomials $Q_n$ are curiously similar to binomial expansions: $$Q_0=1 $$ $$Q_1=1 $$ $$Q_2=q + 1 $$ $$Q_3 = q^3+3q+1 $$ $$Q_4=q^6+4q^3+3q^2+6q+1 $$ $$Q_5=q^{10}+5q^6+10q^4+10q^3+15q^2+10q+1 $$ $$Q_6=q^{15}+6q^{10}+15q^7+25q^6+60q^4+35q^3+45q^2+15q+1 $$ $$Q_7=q^{21}+7q^{15}+21q^{11}+21q^{10}+35q^9+105q^7+105q^6+105q^5+210q^4+140q^3+105q^2+21q+1 $$

  • 1
    $\begingroup$ There is a question here on MO about your last series $\endgroup$ Dec 27 '16 at 13:48
  • 2
    $\begingroup$ bricolage?${}{}$ $\endgroup$ Dec 27 '16 at 15:41
  • 1
    $\begingroup$ @Pietro Majer thanks a lot this is definitely a huge progress in what I was thinking about this recurrent relation. It appears directly, so I mentioned as much as I knew. Also I have the following question, b/c I am very familiar with generating functions: I observed that for larges $p$ (let's say from 0.6 to 1) polynomial are close to $p^{\binom{n}{2}}$. Is there a way to prove this using generating functions? $\endgroup$
    – Eugene
    Dec 27 '16 at 19:45
  • 3
    $\begingroup$ @GerryMyerson I'm guessing 'bricolage' here is a free way of saying "fiddling around" -- doing this or that to massage it into the desired form. $\endgroup$
    – Todd Trimble
    Dec 28 '16 at 1:36
  • 2
    $\begingroup$ According to Lévi-Strauss, bricolage is the characteristic trait of the primitive/wild thinking --producing something that is suggested by what is available on the ground, combining it conveniently, as opposed to the modern scientific thinking, that creates its own instruments and methods :D $\endgroup$ Dec 28 '16 at 8:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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