Final exan (d) Use induction to prove that Bn is uniformly distributed on (0, 1, 2,.,n-1 You may assume your answers to the preceding problem parts without justification Solution. We use induction. Let P(n)be the proposition that Bn is uniformly dis- ibuted on the set (0, 1, 2 Base case. The random variable Bi is always equal to O, so it is uniformly distributed Inductive step. Assume that the random variable Bn is uniformly distributed on the set 0, 1, 2,..., n-1 and consider the random variable B,+1. There are three cases n Pr(Br 0) n+1 Pr(Bn=0 n+in 1 n+1 n Pr(B +1 Pr(Bn=n-1) n+ln Pr(Bn+1= k n-k1 k 1 1n+n+1 +1 n each case, the first equation comes from the preceding problem parts. We use the induction hypotheses on the starred lines. The remaining steps are simplfica tions. This shows that Bn+i is uniformly distributed and the claim follows from the principle of inductionFinal Exam 10 (d) Use induction to prove that Bn is uniformly distributed on {0, 1, 2, . . . , n − 1}. You may assume your answers to the preceding problem parts without justification. Solution. We use induction. Let P(n) be the proposition that Bn is uniformly dis￾tributed on the set {0, 1, 2, . . . , n − 1}. Base case. The random variable B1 is always equal to 0, so it is uniformly distributed on {0}. Inductive step. Assume that the random variable Bn is uniformly distributed on the set {0, 1, 2, . . . , n − 1} and consider the random variable Bn+1. There are three cases: n Pr (Bn+1 = 0) = Pr (Bn = 0) n + 1 n 1 = (*) n + 1 n 1 = n + 1 n Pr (Bn+1 = n) = Pr (Bn = n − 1) n + 1 n 1 = (*) n + 1 n 1 = n + 1 k Pr (Bn+1 = k) = n − k Pr (Bn+1 = k) + Pr (Bn+1 = k − 1) n + 1 n + 1 1 k 1 = n − k + (*) n + 1 n n + 1 n 1 = n + 1 In each case, the first equation comes from the preceding problem parts. We use the induction hypotheses on the starred lines. The remaining steps are simplfica￾tions. This shows that Bn+1 is uniformly distributed, and the claim follows from the principle of induction