A recurrence is any recursively defined function f with domain ℕ that computes numbers. To solve a recurrence f we must find an expression for the general term f(n) that is not recursive. In a simple recurrence, f only appears once on the right side of the general equation for f(n). What method(s) should we use to solve a simple recurrence? Select all that apply.

Match each term to the correct definition.

Suppose you are on a game show. There is a prize behind one of three doors, and you are asked to choose a door.

After you choose, suppose the host opens one of the remaining two doors and shows you that there is no prize behind it. You are given the choice to keep your original door or choose the remaining door instead.

Statistically speaking, what should you do?

You are going into battle with Team Aqua, and you must select a team of 5 unique Pokemon. You have 15 Pokemon to choose from. How many different line-ups are possible?

You should assume that order is significant since Pokemon at the front of your party will go into battle first. In other words, these 2 line-ups would be considered different even though they contain the same Pokemon:

Meowth, Squirtle, Diglett, Pikachu, Clefairy

Squirtle, Meowth, Clefairy, Diglett, Pikachu

Suppose that 1% of Pokemon trainers have a Charmander and 2% of Pokemon trainers have a Squirtle. Further, it is known that 0.1% of trainers have both a Charmander and a Squirtle. If we learn that a certain trainer has a Squirtle, what is the probability that this trainer has a Charmander?

Suppose S = {a, b, c, d, e}.

How many three-element subsets does S have?

In how many ways can four pokemon be selected from a collection of charmanders, squirtles, and torchics?

Repetition is allowed, but order is not important. In other words,

[torchic, torchic, squirtle, squirtle] = [squirtle, torchic, squirtle, torchic]

Transform the following summation into a closed form (if possible).

Evaluate the expression by expanding it into a sum of terms.

Suppose there are 8 possible solutions to some problem. If we use a binary decision tree to represent an algorithm that solves the problem, what is the optimal depth?