Return to Question

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.

[edit]

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.

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.

[edit]

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.

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.

[edit]

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} 2^{\binom{t}{2}} P_t(\frac{1}{2}) $$ and leads to Bell number.

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.

[edit]

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.

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.

[edit]

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.

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.

[edit]

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} 2^{\binom{t}{2}} P_t(\frac{1}{2}) $$ and leads to Bell number.