Sum of discrete non-uniform random variable and a Bernoulli is non-uniform Let $X$ be a non-uniform discrete random variable over $\{0,1,\dots,n\}$, and $Y$ be a Bernoulli random variable, not necessarily independent of $X$.
Is this information sufficient to conclude that $X + Y$ is non-uniform over $\{0,1,\dots,n+1\}$? If not, what would be a counter-example?
Edit: And what if $Y$ is independent of $X$?

I'll find all solutions to the independent case.  Let $P(X=i) = p_i$ and $P(Y=1) = r$.  Then consider the probability generating functions of $X$ and $Y$.  These are $f_X(z) = p_0 + p_1 z + p_2 z^2 + \cdots + p_n z^n$ and $f_Y(z) = (1-r) + rz$.  Then the pgf of $Z = X + Y$ is
$$ f_Z(z) = f_X(z) f_Y(z) = (p_0 + p_1 z + \cdots + p_n z^n) ((1-r) + rz). $$
For $X + Y$ to be uniform this must be $(1 + z + \cdots + z^{n+1}) / (n+2)$.  So we want to know: are there nonnegative real $p_0, p_1, \cdots, p_n, r$ such that, for all $z$,
$$ (p_0 + p_1 z + \cdots + p_n z^n) ((1-r) + rz) = {1 + z + \cdots + z^{n+1}\over {n+2}}. $$
Now $1 + z + \cdots + z^{n+1} = (1-z^{n+2})/(1-z)$, so it suffices to find $p_0, p_1, \ldots, p_n, r$ such that
$$ (p_0 + p_1 z + \cdots + p_n z^n) ((1-r) + rz) (1-z) = {1 - z^{n+2} \over (n+2)}$$
To be equal as polynomials, the two sides must have the same zeroes.  The zeroes of the right-hand side are the $(n+2)$ roots of unity. 
If $n$ is odd, then only one of these is real. But the left-hand side has at least two real roots, coming from the factors $((1-r) + rz)$ and $1-z$, so we have no solution.
If $n$ is even then the right-hand side has two real roots $z = \pm 1$.  The right-hand side has the real root $z = 1$ coming from the factor $1-z$.   If $r = 1/2$, it will also have the root $z = -1$ coming from the factor $(1-r) + rz = (1/2 + z/2)$.  So any solution has $r = 1/2$.
Then we get
$$ (p_0 + p_1 z + \cdots + p_n z^n) = {1-z^{n+2} \over (n+2) (1-z)(1+z)/2} $$
or after some rearrangement
$$ (p_0 + p_1 z + \cdots + p_n z^n) = {2 \over n+2} {1-z^{n+2} \over 1-z^2}. $$
Doing the division on the right-hand side we get
$$ p_0 + p_1 z + \cdots + p_n z^n = {2 \over n+2} (1 + z^2 + z^4 + \cdots + z^n) $$
and so we conclude that $X$ must be uniform on $\{ 0, 2, 4, \ldots, n \}$.  
So the only solutions when $X$ and $Y$ are independent have $X$ uniform on $\{ 0, 2, 4, \ldots, n \}$ for even $n$, and $Y$ uniform on $ \{0, 1\}$.  If $n = 4$ this is the example that kimchi lover gave. 
