Got such a task at the exam. Any ideas how to solve it?
Consider the set $ \{1,\dots,n\} $. Lets perform sequential pairwise independent Bernoulli trials with success probability $ \frac{1}{2}$.
If we get success at $\textbf{i}$-step, we take $\textbf{i}$ out and put into the projected set $A$ then go to $i+1$th trial. If not, we simply go on to the next trial.
In the end we get a random set $A$ consisting of the elements that were taken out. It can be either null or equal to all set $\{1,\dots,n\}$, or be any other.
The difference of two sets $A,B\subset \{0,1,2,\ldots,n-1\}$ is a set $A-B=\{a-b:a\in A, b\in B\}$ (the difference of two elements of this set is considered as the difference of two natural number. Note that $A-B$ can contain elements that don't belong to the set $\{0,1,\ldots, n-1\}$, but always is a subset of $\{-n+1,-n+2,\ldots,n-2,n-1\}.$.
Take the set $A$ randomly generated by the scheme described above and find linear recurrence equation with constant coefficients at probability $p_n={\rm P}(3\notin A-A)$
As I understood it means that the set A should not contain two objects the difference between which equals 3.
I tried to consider options when the last $n-1$ element is or is not included in the resulting set $A$ but didn't move any further than $p_n = \frac{1}{2} p_{n-1} + something$. $something$ is when $n-1$ is in set $A$.
Edit: With help of @GCab I tried to process binary string recursively from the end and got such recurrence: $p_n = \frac{1}{2} p_{n-1} + \frac{1}{2}(\frac{1}{2}(\frac{1}{2} p_{n-6}+ \frac{1}{2}p_{n-5}) + \frac{1}{2}(\frac{1}{2}d_{n-2} + \frac{1}{2}p_{n-3}))$ where $d_k = \frac{1}{2}d_{k-2} + \frac{1}{2}p_{k-2}$ Is it correct? It seems to me a little bit strange, ohh inner recurrence?
The comment about $|3|$ is instead helpful.
That means that you can take your sequence of trials as a binary string of length $n$.
Then your problem becomes to count the strings that do (/ do not) have
(amended thanks to Ian's comment)
** two $1$'s separated by exactly two characters whichever, i.e. the $(1,x,x,1)$ subsequence**.
because you are taking the difference between any two elements of $A$, which therefore could contain other successes in between.
If you were taking the difference between two consecutive elements of $A$, then the pattern would be $(1,0,0,1)$.
That premised, we are dealing with the general problem of finding the number of strings (in this case, binary) that contain a given substring or set of substrings.
It is not an easy task, but there is a general approach as described in M_ Scheuer's answer to this post.
Also the number of strings containing the substring $(1,x,x,1)$ is the OEIS seq. V.