A positive integer $n$ is drawn at random with probability $P(n) = \frac{1}{2^n}$ for $n = 1, 2, 3, \ldots$
Let $A_k$ denote the event that the drawn number is divisible by $k$.
Compute $P(A_2 \cup A_3)$ -- the probability that the number is divisible by 2 or 3.
For integers $p, q > 2$, prove that the events $A_p$ and $A_q$ are not independent.
Hints
For any $k$, the probability of divisibility by $k$ is a geometric series: $P(A_k) = \sum_{m=1}^{\infty} 2^{-mk}$. Sum it.
For the union in Part 1, use inclusion-exclusion. The intersection $A_2 \cap A_3$ equals $A_{\text{lcm}(2,3)} = A_6$.
For the independence proof, you need to show $(2^p - 1)(2^q - 1) \neq 2^L - 1$ for $L = \text{lcm}(p,q)$. Try showing the product lies strictly between two consecutive powers of 2.
Worked Solution
How to Think About It: The distribution $P(n)=1/2^n$ puts exponentially decaying weight on the positive integers. Divisibility by $k$ selects the sub-series $n=k,2k,3k,\dots$, a geometric series we can sum in closed form: $P(A_k)=1/(2^k-1)$. Part 1 is then inclusion-exclusion. Part 2 asks to prove $A_p,A_q$ are never independent for $p,q>2$. Independence would force $(2^p-1)(2^q-1)=2^{L}-1$ with $L=\mathrm{lcm}(p,q)$. The right idea is a *size* argument: the product is squeezed into the open interval $(2^{p+q-1},2^{p+q})$, the only power of
$ that could make
^L-1$ land there is
^{p+q}$ (forcing $L=p+q$), and then a direct comparison shows the product is strictly less than
^{p+q}-1$ -- a contradiction.
Quick Estimate: $P(A_2)=\tfrac13$, $P(A_3)=\tfrac17$, and the overlap is $P(A_6)=\tfrac1{63}$. So $P(A_2\cup A_3)=\tfrac13+\tfrac17-\tfrac1{63}\approx0.46$. (Note $P(A_2)P(A_3)=\tfrac1{21}\ne\tfrac1{63}=P(A_6)$, so even $A_2,A_3$ are not independent -- foreshadowing Part 2.)
Approach: Sum the geometric series for $P(A_k)$, apply inclusion-exclusion for Part 1, and for Part 2 assume independence, reduce it to the integer identity $(2^p-1)(2^q-1)=2^{L}-1$, and refute it: bound the product strictly between
^{p+q-1}$ and
^{p+q}$ to force $L=p+q$, then compare
^{p+q}-1$ against the exact value of the product.
Independence would require these to be equal, i.e.
$(2^p-1)(2^q-1)=2^{L}-1. \tag{$\star$}$
Write $N=(2^p-1)(2^q-1)=2^{p+q}-2^p-2^q+1$ and bracket it between consecutive powers of
$ (valid for $p,q\ge3$):
Upper bound: since
^p+2^q-1>0$, we have $N=2^{p+q}-(2^p+2^q-1)<2^{p+q}$.
Lower bound: $N>2^{p+q-1}$ is equivalent to
^{p+q-1}>2^p+2^q-1$; dividing by
^{p+q-1}$ this reads
>2^{1-q}+2^{1-p}-2^{1-p-q}$, and for $p,q\ge3$ the right side is at most
^{-2}+2^{-2}=\tfrac12<1$. (Smallest case $p=q=3$: $N=49$ and
^5=32<49<64=2^6$.)
So
^{p+q-1}<N<2^{p+q}$.
The bracketing alone is not enough, and this is precisely where the naive argument breaks: a number can lie strictly between two consecutive powers of
$ and *still* be one less than a power of
$ -- for instance $63\in(32,64)$ yet $63=2^6-1$. So we must use the bounds more carefully. Suppose $(\star)$ held, so $N=2^{L}-1$, equivalently
^{L}=N+1$. From
^{p+q-1}<N<2^{p+q}$ (integers, so $N\le 2^{p+q}-1$) we get
$2^{p+q-1}<N+1\le 2^{p+q}.$
The only power of
$ in the half-open interval $(2^{p+q-1},\,2^{p+q}]$ is
^{p+q}$ itself, so
^{L}=2^{p+q}$, i.e. $L=p+q$. That would make
^{L}-1=2^{p+q}-1$. But the exact value of the product is strictly smaller:
$N=2^{p+q}-2^p-2^q+1<2^{p+q}-1,$
because
^p+2^q>2$ for $p,q\ge3$ (indeed
^p+2^q\ge16$). Hence $N\ne 2^{p+q}-1=2^{L}-1$, contradicting $(\star)$. Therefore $P(A_p\cap A_q)\ne P(A_p)P(A_q)$, so $A_p$ and $A_q$ are not independent.
*(Remark: the hypothesis $p,q>2$ is used in the lower bound and in
^p+2^q>2$. The whole argument hinges on pinning $L=p+q$ from the bracketing and then comparing the exact value $N=2^{p+q}-2^p-2^q+1$ to
^{p+q}-1$ -- not on the bracketing by itself.)*
Answer: 1. $P(A_2\cup A_3)=\dfrac{29}{63}$. 2. For $p,q>2$, independence would force $(2^p-1)(2^q-1)=2^{\mathrm{lcm}(p,q)}-1$. Writing $N=(2^p-1)(2^q-1)=2^{p+q}-2^p-2^q+1$, the bounds
^{p+q-1}<N<2^{p+q}$ force any solution to satisfy $\mathrm{lcm}(p,q)=p+q$; but then
^{\mathrm{lcm}(p,q)}-1=2^{p+q}-1>N$, a contradiction. Hence $A_p$ and $A_q$ are never independent.
Intuition
Under a uniform distribution on integers, divisibility by coprime numbers would be independent -- knowing a number is divisible by 3 tells you nothing about divisibility by 5. But this geometric distribution $P(n) = 1/2^n$ assigns exponentially more weight to small numbers, and small numbers have different divisibility patterns than large ones. This coupling through the weighting scheme destroys independence.
The deeper point is that independence is fragile -- it depends not just on the events but on the probability measure. Change the measure, and events that were independent become dependent. This shows up constantly in quantitative finance: under the physical measure, two assets might appear uncorrelated, but under a risk-neutral measure (which reweights states), they can become highly dependent. The lesson is to always check independence under the specific measure you're working with, not assume it carries over from another context.