# Probability of a sum being even

Say for every natural number z $$\ge$$ 1, we choose a number $$a_z$$ from the set {$${1,...,z}$$} randomly with equal probability for each number 1 to z. For example, $$a_3$$ we can choose 1, 2, or 3 all with probability 1/3. If b $$\ge$$ 2 what is the probability that the sum of $$a_1$$ + ... + $$a_b$$ is even for any b.

I know that whenever b is an even number the probability that the number chosen is odd is 1/2. I tried to use the fact that $$a_1$$ has to be 1 to try to see when I can have the sum of two odds since that is even. However, I am stuck on figuring out the probability that the entire sum is even.

• Why did you delete all the text in the question? I have rolled it back to your original. – Henry Mar 10 at 17:47

Let's call the sum $$S_b = a_1+a_2+\cdots+a_{b-1}+a_b$$.
If $$b$$ is even and $$b\ge 2$$ then the probability is $$\frac12$$ that $$a_b$$ is odd and so changes the parity of the sum, and $$\frac12$$ that $$a_b$$ is even and so does not change the parity of the sum, making the probability that $$S_b$$ is odd or even $$\frac 12$$ each.
If $$b$$ is odd then $$b-1$$ is even. So as long as $$b-1\ge 2$$, we can now say $$S_{b-1}$$ is equally likely to be odd or even. Meanwhile $$a_b$$ is odd with probability $$\frac{b+1}{2b}$$ and even with probability $$\frac{b-1}{2b}$$. So the probability $$S_b$$ is even given $$b$$ is odd and $$b\ge 3$$ is $$\frac12 \frac{b+1}{2b}+\frac12 \frac{b-1}{2b}= \frac12$$ too.
That leaves the cases $$b=0$$ and $$b=1$$, which are easy to handle.
• When $$b=0$$ then $$S_0=0$$ and even (the empty sum) so $$\mathbb P(S_0 \text{ is even})=1$$.
• When $$b=1$$ then $$S_0=1$$ and odd so $$\mathbb P(S_1 \text{ is even})=0$$.
• When $$b\ge 2$$ then $$\mathbb P(S_b \text{ is even})=\frac12$$.