Sum of identically distributed but not independent Bernoulli's is non-uniform Let $X_1,X_2,\dots$ denote a sequence of identically distributed, exchangeable, but not independent, Bernoulli$(p)$ random variables. If there exists $n>0$ such that
$$
\sum_{i=1}^{n}X_i
$$
is not uniformly distributed on $\{0,1,\dots,n\}$, how can we show that this implies
$$
\sum_{i=1}^{n}X_i + X_{n+1}
$$
is not uniformly distributed on $\{0,1,\dots,n+1\}$? If $p \ne 1/2$ then the claim follows by expectations, so we can consider $p=1/2$.
 A: First, some notations: for every $n$, let $X_{1:n}=(X_1,X_2,\ldots,X_n)$, and, for every word $w=(w_1,w_2,\ldots,w_n)$ in $\{0,1\}^n$, let $|w|=w_1+w_2+\cdots+w_n$.  Now, to the proof, which uses crucially the exchangeability hypothesis.
Assume that, for some $n\geqslant1$, $|X_{1:n+1}|$ is uniformly distributed on $\{0,1,\ldots,n+1\}$. 
Then, by exchangeability, for every word $w$ in $\{0,1\}^{n+1}$, $P(X_{1:n+1}=w)$ depends only on $|w|$. For each $k$ in $\{0,1,\ldots,n+1\}$, there are ${n+1\choose k}$ words $w$ in $\{0,1\}^{n+1}$ such that $|w|=k$, hence, for every word $w$ in $\{0,1\}^{n+1}$ such that $|w|=k$, $$P(X_{1:n+1}=w)={n+1\choose k}^{-1}P(|X_{1:n+1}|=k)=(n+2)^{-1}{n+1\choose k}^{-1}$$
For every word $v$ in $\{0,1\}^n$, the event $[X_{1:n}=v]$ is the disjoint union of the events $[X_{1:n}=v,X_{n+1}=0]$ and $[X_{1:n}=v,X_{n+1}=1]$. 
If $|v|=k$ for some $k$ in $\{0,1,\ldots,n\}$, then $|v0|=k$ and $|v1|=k+1$, hence $$P(X_{1:n}=v)=(n+2)^{-1}{n+1\choose k}^{-1}+(n+2)^{-1}{n+1\choose k+1}^{-1}$$
Now, it happens that $$(n+2)^{-1}{n+1\choose k}^{-1}+(n+2)^{-1}{n+1\choose k+1}^{-1}=(n+1)^{-1}{n\choose k}^{-1}\tag{$\ast$}$$ hence $$P(X_{1:n}=v)=(n+1)^{-1}{n\choose k}^{-1}$$ Summing these over the ${n\choose k}$ words $v$ in $\{0,1\}^n$ such that $|v|=k$, one gets, for every $k$ in $\{0,1,\ldots,n\}$, $$P(|X_{1:n}|=k)=(n+1)^{-1}$$
Thus, if $|X_{1:n+1}|=X_1+X_2+\cdots+X_{n+1}$ is uniformly distributed on $\{0,1,\ldots,n+1\}$, then $|X_{1:n}|=X_1+X_2+\cdots+X_n$ is uniformly distributed on $\{0,1,\ldots,n\}$.
By contraposition, this proves the desired statement -- and also that, as soon as $|X_{1:n}|=X_1+X_2+\cdots+X_{n}$ is uniformly distributed on $\{0,1,\ldots,n\}$ for some $n\geqslant1$, then $|X_{1:1}|=X_1$ is uniformly distributed on $\{0,1\}$, and, again by exchangeability, every $X_n$ is uniformly distributed on $\{0,1\}$, that is, necessarily, $p=\frac12$.
Exercise: Prove $(\ast)$.
A: Here is a large hint/outline.
A good method is to prove the contrapositive. Letting $S_{n}=\sum_{i=1}^n X_i$,  assume that $S_{n+1}$ is uniformly distributed over $\{0,1,\dots,n+1\}$, and prove that $S_n$ is uniform as well. 
To prove this, use the decomposition 
$$
P(S_n=k) = P(S_n=k\cap X_{n+1}=0)+P(S_n=k\cap X_{n+1}=1)\tag{*}
$$
We need to somehow relate the events on the RHS to events of the form $\{S_{n+1}=h\}$, whose probabilities are known to be $\frac1{n+2}$. 
If we consider our sample space to be the set of sequences of $n+1$ zeroes and ones, then $\{S_n=k\}\cap \{X_{n+1}=0\}$ consists of all $\binom{n}k$ sequences ending in a $0$ and consisting of $k$ ones. By exchangeability, these events are all equally likely. In particular, letting $E$ be the event that $X_i=1$ for $i=1,2,\dots,k$ and $X_i=0$ for $i=k+1,k+2,\dots,n+1$ (the string $11\dots100\dots0$), then
$$
P(S_n=k\cap X_{n+1}=0) = \binom{n}k\cdot P(E)
$$
On the other hand, $E$ is a subset of the event $\{S_{n+1}=k\}$, which consists of $\binom{n+1}{k}$ equally likely sequences, so we also have
$$
\frac1{n+2}=P(S_{n+1}=k)=\binom{n+1}k\cdot P(E)
$$
The last two equations allow you to eliminate $P(S_n=k\cap X_{n+1}=0)$ in $(*)$. You can do something similar to eliminate $P(S_n=k\cap X_{n+1}=1)$.
