Here is my first #TorqueGroup post! Please tell me anything you like/dislike about it, if anything is unclear, or anything else!

Recursion

Recursion is using smaller cases to construct larger cases.

Here are some signs that recursion might be a good method to attack a problem:

1. The problem asks for the value of a large case, and you can determine small values or they are given.

2. There is a clear connection between small cases and large cases.

Here are some steps helpful when applying recursion to a problem:

1. Analyze small cases.

2. Try to construct larger cases using smaller cases.

3. Make a conjecture about a connection between a larger case and the case[s] smaller than it.

4. Prove your conjecture.

5. Determine the answer using the connection you found.

Let us begin with a simple example:

A collection of 8 cubes consists of one cube with edge-length $k$ for each integer $k$, $1\le k\le 8$. A tower is to be built using all 8 cubes according to the rules:

• Any cube may be the bottom cube in the tower.

• The cube immediately on top of a cube with edge-length $k$ must have edge-length at most $k+2$.

Let $T$ be the number of different towers than can be constructed. What is the remainder when $T$ is divided by 1000? (AIME)

Your initial instinct may be to try casework based on which position a certain block is in, or maybe you thought that complementary counting was a good approach. However, recursion turns out to be a very fruitful approach to solve this problem. Looking back at our signs:

The problem asks for the value of a large case, and you can determine small values or they are given.

Yes, the problem asks about a tower with 8 cubes, and finding the number of towers of 1, 2 and even 3 is very simple, as the restriction doesn't matter.

There is a clear connection between small cases and large cases.

Yes, to get from 4 cubes to 5 cubes, simply add a cube, although the method of doing that may be slightly trickier.

Let $T_n$ be the number of towers of $n$ cubes. Let us apply our steps above:

Analyze small cases.

With 1 cube, there is clearly only 1 possible tower, so $T_1=1$. With 2 cubes, there are $2$ possible towers, and $T_2=2$. With 3 cubes, there are $6$ possible towers, and $T_3=6$.

Try to construct larger cases using smaller cases.

If we have 3 cubes, and want to place the 4th, where can we put it? We can clearly put it on the bottom by the first rule in the problem. Following that thought, we can put it on top of the 2 or the 3, but not the 1. Then, we have 3 places we can put the 4th cube, and so $T_4=T_3\cdot 3=6\cdot 3=18$.

If we have 4 cubes, and want to place the 5th, where can we put it? We can put it on the bottom, or we can put it on top of the 3 or the 4. Therefore, there are 3 places we can put the 5th cube, and $T_5=T_4\cdot 3=18\cdot 3=54$.

Make a conjecture about a connection between a larger case and the case[s] smaller than it.

We can conjecture that $T_k=3T_{k-1}$ for $k\ge 3$. Luckily, this connection only depends on the previous term, so the work is easier.

Prove your conjecture.

If $k\ge 3$, then the $k^{th}$ cube can go on the bottom, or on top of the $(k-1)^{th}$ cube or the $(k-2)^{th}$ cube. Then, we conclude that $T_k=3T_{k-1}$, as for each tower with $k-1$ cubes, the $k^{th}$ cube can go in 3 places.

Determine the answer using the connection you found.

Finally, $T_2=2$, and $T_8=3(T_7)=3^2(T_6)=\cdots=3^6(T_2)=1\boxed{458}$.

Well, that wasn't that bad, was it? I guarantee casework and other methods would have taken longer. Now that we have seen a more basic application of recursion, let us dive in deeper with another problem.

In how many ways can 7 teams place in a tournament if ties are allowed?

First, let us try to understand the problem, and I think a good way to go about that is by listing some possible orderings. Let the teams be numbered 1 through 7. We could have 1 be first, 2 be second, and so on till 7 which is last, or we could have 1 and 3 and 6 tie for first, and the other four teams tie for second, or we could... You know what, I'm starting to think that there might be a few too many possibilities to list. In fact, even without ties, there are $7!=5040$ possibilities.

Now, let us try casework. If there are no ties, there are $5040$ possibilities. lf there is one tie between two teams for first, we first pick the two teams that tie, and then order the remaining five teams. In fact, the number of possible placements, assuming teams are indistinguishable, is equal to the number of ordered partitions of $7$, which you will soon see in problem number 1 below. I'll tell you this much: it is way too large to do by hand.

As this post is about recursion, I hope you are now thinking about how to apply recursion to this problem. Sign number 1 (asks for a large case, small cases are determinable) is satisfied. Number 2 (connect larger cases with smaller cases) is also satisfied, as all we do is add a team. Now, let us try to think about how a recursion would work...

If we have 6 teams, and want to place the 7th, where can be put it? If there are no ties in the 6 teams, this question is not so difficult. We can have 7 tie with any of the other 6 teams, or we can have it not tie, and be first, second, third, ..., or last. But what if there are ties? Say there is one tie. Then, we can have 7 tie with any of the 5 (do you see why 5 now?) other places, or it can not tie, being first, second, third, ..., or last. Continuing this train of thought, if we knew how many possibilities there were for 6 teams in 4 "groups," then we could place the 7th team tying with one of the 4 groups, or it could be alone in 5 places. This starts to sound like a recursion we can do!

To generalize, say we have $n$ teams in $k$ groups in $x$ different ways. We can have $n+1$ teams in $k$ groups by adding a team to any of the $k$ existing groups, giving $kx$ ways, and we can have $n+1$ teams in $k+1$ groups by adding a team alone in $k+1$ different locations, giving $(k+1)x$ ways.

Now, let us start a recursion. Let $f(n,k)$ be the number of ways $n$ teams can place into $k$ spots, and define $f(n,0)=0$ and $f(n,k)=0$ if $k>n$. By our earlier logic, $f(n+1,k)=(k)f(n,k-1)+(k)f(n,k)=k(f(n,k-1)+f(n,k))$ For the base case, we can see that $f(1,1)=1$. Let us make a table, where $n$ goes down the side and $k$ is on the top: $\begin{array}{| l | l | l | l | l | l | l | l |} \hline & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ \hline 1 & f(1,1) & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline 2 & f(2,1) & f(2,2) & 0 & 0 & 0 & 0 & 0 \\ \hline 3 & f(3,1) & f(3,2) & f(3,3) & 0 & 0 & 0 & 0 \\ \hline 4 & f(4,1) & f(4,2) & f(4,3) & f(4,4) & 0 & 0 & 0 \\ \hline 5 & f(5,1) & f(5,2) & f(5,3) & f(5,4) & f(5,5) & 0 & 0 \\ \hline 6 & f(6,1) & f(6,2) & f(6,3) & f(6,4) & f(6,5) & f(6,6) & 0 \\ \hline 7 & f(7,1) & f(7,2) & f(7,3) & f(7,4) & f(7,5) & f(7,6) & f(7,7) \\ \hline \end{array}$

To finish, we simply fill in values (don't mess up here!): $\begin{array}{| l | l | l | l | l | l | l | l |} \hline & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ \hline 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline 2 & 1 & 2 & 0 & 0 & 0 & 0 & 0 \\ \hline 3 & 1 & 6 & 6 & 0 & 0 & 0 & 0 \\ \hline 4 & 1 & 14 & 36 & 24 & 0 & 0 & 0 \\ \hline 5 & 1 & 30 & 150 & 240 & 120 & 0 & 0 \\ \hline 6 & 1 & 62 & 540 & 1560 & 1800 & 720 & 0 \\ \hline 7 & 1 & 126 & 1806 & 8400 & 16800 & 15120 & 5040 \\ \hline \end{array}$ and the answer is $1+126+1806+8400+16800+15120+5040=\boxed{47293}$.

Problems:

1. Find the number of ordered partitions of $10$ where an ordered partition of $n$ is a tuple of positive integers $(a_1,a_2,\cdots,a_k)$ such that $a_1+a_2+\cdots+a_k=n$.

2. A mail carrier delivers mail to the nineteen houses on the east side of Elm Street. The carrier notices that no two adjacent houses ever get mail on the same day, but that there are never more than two houses in a row that get no mail on the same day. How many different patterns of mail delivery are possible? (AIME)

3. In how many ways can 7 teams place in a tournament if ties are allowed? Try this problem with a single recursion that doesn't depend on groups. Hint: use more than one previous value in the recursion.

4. See here.

Next week, I will write a post about recursion in computer science.

In two weeks, we will learn how to solve expressions such as $T_k=3T_{k-1}$, which are called recurrence relations.

If you want more problems to work on, you can look up #RecurrenceRelations.