# Todai Entrance Exam: Math 2018 – Problem 3

**(1)** We prove and (note that and , I doubt if zero can be considered as an even number though).

Base case:

- .
- if a red card was taken.
- if a white card was taken.

So and are true for .

Induction step: Let .

- if a red card was taken.
- if a white card was taken.

So (with or ).

- if a red card was taken.
- if a red card was taken.

So (with or ).

So the statement follows.

**(2)** From (1), we proved that if and it is already given that (because ). Now we prove that for with .

Base case:

- There are 4 possible combinations of card colours pulled in the first and second times which lead to different values of :

First pull | Red | White |

Second pull | ||

Red | -1 | 1 |

White | 1 | -1 |

- We have: and . Therefore, and .

So .

Induction step: Given , prove that .

.

There are 2 possible values of : (probability: ) and (probability: ).

There are 4 possible combinations of card colours pulled in the th and th time yielding 2 possible values of product : (probability: ) and (probability: ).

if and only if and both equals or and both equals .

Probability of and both equals : .

Probability of and both equals : .

So the statement follows: .

Now comes to , we see that . Therefore, for with :

We also proved from (1) that for .

So in summary:

**(3)** We find the closed form of (thanks to my labmate for the closed form solution).

- Probability of : if is even, otherwise.
- Probability of : if is even, otherwise.
- Probability of : if is odd, otherwise.
- Probability of : if is odd, otherwise.

**(4)** If is even, then:

If is odd, then:

As the probability for to be even equals the probability for to be odd and they are , we arrive the solution:

Q.E.D

**(5)** Prove that .

Base case:

- .
- If the red card is taken in the first pull: . So, .
- If the white card is taken in the first pull: . So, .

So the statement holds true for .

Induction step: Given , prove that .

- If the red card is taken in the th time: .
- If the white card is taken in the th time: .
- If the red card is taken in the th time: .
- If the white card is taken in the th time: .

So the statement follows.

Therefore .

**(6)**

**(7)**