Homework: Homework 10 Recurrences

Assigned

• April 21, 2026

Due

• April 24, 2026 10:00pm

Problem 1: Down for the Count

Consider the following Racket code:

def f(n):
    for i in range(int(n/2)):
        print("!")
    for i in range(n):
        for j in range(n):
            print("!")
            print("!")

def g(n):
    if n <= 1:
        pass # i.e., do nothing
    else:
        print("!")
        print("!")
        print("!")
        g(n-2)

1. Give two combinatorial descriptions for the number of !s printed by f, the first using summation notation, and the second, an explicit formula without the use of summation notation. Your description should be a function of the input n.

2. Give a recurrence relation describing the number of !s printed by g.

   (Hint: Your recurrence relation’s case should account for the fact that the recurrence goes down by two!)

3. Derive a closed-form expression for this recurrence relation and prove that the closed-form expression is equivalent to the recurrence. For this step, assume that $n$ is even.

   (Hint: When proving your formula correct, note that because the recurrence ticks down by two, standard mathematical induction will not suffice.)

4. Adapt your answer from the previous part to account for any $n \in \mathbb{N}$.

   (Hint: There are two ways to proceed. You may consider creating an additional recurrence to your solution for the case when $n$ is odd. It is also possible to come up with a single recurrence that uses the floor function $\lfloor r \rfloor$ which rounds real number $r$ down to the nearest whole number. For example $\lfloor 4.7 \rfloor = 4$.)

Problem 2: Cash Money

In the game of roulette, players bet on the outcome of a ball randomly landing in 38 distinct slots labeled with the numbers $1$–$36$, $0$, and $00$. The numbers in the range $1$–$36$ are furthermore colored as follows:

Give combinational descriptions (i.e., unsimplified formulae) for each of the required values.

1. What is the probability of winning a “00” bet (where the ball lands on $00$)?
2. What is the probability of winning an “odd” bet (where the ball lands on an odd number)?
3. What is the probability of winning either a “1st dozen” bet (where the ball lands on a number in the range 1–12) or a red bet (where the ball lands on a red number)?
4. What is the probability of winning both an “even” bet (where the ball lands on an even number, 0 and 00 do not count as even) and a “3rd dozen” bet (where the ball lands on a 25–36)?
5. Let $X$ be a random variable describing the pay-off of a single set of bets in dollars. What is the expected value of placing both a “black” bet (where the ball lands on a black number) and a “1st dozen bet” bet if the pay-off for the black bet is 1 dollar and the pay-off for the “1st dozen bet” is 2 dollars?