This question is about investigating two sequences involving paired parentheses and…
MATHEMATICS · Multi-part · AoPS · Mathematics · Follow the Rules · Follow the Rules
Problem
This question is about investigating two sequences involving paired parentheses and using links between them to generate a formula. In computer science, a useful validity check for mathematical expressions is to check that all open parentheses match closed parentheses. An is the number of possible expressions (not necessarily correct) with n pairs of parentheses. For example, when n=1 there are two possible expressions: () or )( So A1=2 . Bn is the number of correct expressions with n pairs of parentheses. For example, when n=1 the only correct expression is (), so B1=1 . You are given that B8=1430 .
(a) Show that A2=6 .
(b) When n=8 :
(i) How many characters are in the expression?
(ii) How many of these positions should be chosen to contain open '(' parentheses?
(iii) Hence find A8 and state a general expression for An .
(c) (i) Show that B2=2 .
(ii) Find B3 .
(d) There is a relationship between An and Bn of the form
Bn=f(n)An.
Suggest an appropriate function for f(n) and hence suggest an expression for Bn .
(e) It can be shown that Bn+1=n+24n+2Bn . Use this result to prove by induction your conjecture from part d.
(f) A corrupted computer file includes an expression involving 20 pairs of brackets. The corruption results in the order of the brackets being switched at random.
What is the probability that the end result still has brackets which form a 'correct expression'?
(g) Asher and Elsa are running in an election. 100 voters cast their vote one at a time, and a running total is kept. At the end of the voting the result is a tie with each candidate getting 50 votes.
What is the probability that Asher is never ahead of Elsa at any point during the count?
Justify your answer.
(a) Show that A2=6 .
(b) When n=8 :
(i) How many characters are in the expression?
(ii) How many of these positions should be chosen to contain open '(' parentheses?
(iii) Hence find A8 and state a general expression for An .
(c) (i) Show that B2=2 .
(ii) Find B3 .
(d) There is a relationship between An and Bn of the form
Bn=f(n)An.
Suggest an appropriate function for f(n) and hence suggest an expression for Bn .
(e) It can be shown that Bn+1=n+24n+2Bn . Use this result to prove by induction your conjecture from part d.
(f) A corrupted computer file includes an expression involving 20 pairs of brackets. The corruption results in the order of the brackets being switched at random.
What is the probability that the end result still has brackets which form a 'correct expression'?
(g) Asher and Elsa are running in an election. 100 voters cast their vote one at a time, and a running total is kept. At the end of the voting the result is a tie with each candidate getting 50 votes.
What is the probability that Asher is never ahead of Elsa at any point during the count?
Justify your answer.