Does a bijective function exists behind every recurrence relation?

Question

Consider these 2 questions where recurrence relations can be applied:

Q1) Given an (nxm) where n denotes rows and m denotes columns of a grid, find the number of unique paths ($a_{n,m}$) that goes from the top left corner of the grid to the bottom right corner of the (nxm) grid. Rule: Can only move downwards or rightwards when travelling on the grid

For Q1) the solution is as follows:

• Base Cases: when n or m is equals to 1 (i.e. $a_{1,m} =1 $ and $a_{n,1} = 1$)
• Considering the last action: There are 2 cases - 1) moving downwards 2) moving rightwards to reach the bottom left corner of the grid. Hence, the recurrence relation is of the form: $a_{n,m} = a_{n-1,m} + a_{n,m-1}$.

But notice here that there is a 1-1 correspondence between $a_{n,m}$ and ($a_{n-1,m} + a_{n,m-1}$) -- for every unique path in $a_{n-1,m}$ we move 1 grid downwards and for every unique path in $a_{n,m-1}$ we move 1 grid rightwards - doing so will create a 1-1 correspondence with the unique paths in $a_{n,m}$.

. .

Q2) The "Tower of Hanoi" Problem where the recurrence relation is of the form: $a_n = 2a_{n-1} + 1$ where $a_n$ denotes the minimum number of steps needed to move n disks from one bar to another bar

. .

Although Q1) seems to have a 1-1 function underneath its recurrence relation, I am wondering whether the same can be argued for the "Tower of Hanoi" problem as I am not able to think of it..

Answer 1

Yes, there is such a bijection.

Let's let $T_1$, $T_2$, $T_3$ denote the three Towers of Hanoi. A single play of the Tower of Hanoi game can be expressed as a finite sequence $p_1,...,p_I$ of ordered pairs $$p_i = (x_i,y_i) $$ where $x_i \ne y_i \in \{1,2,3\}$, where we interpret $p_i$ as take the top piece from $T_{x_i}$ and put it on top of $T_{y_i}$; of course the pieces are linearly ordered by size and the move is legal if and only if the piece moved is smaller than all of the current pieces on $T_{y_i}$. The length of the play $(p_1,...,p_I)$ is $I$.

Let's say that a single play of this game is an $(n,x,y)$-win if the game starts with $n$ pieces on $T_x$ and ends with $n$ pieces on $T_y$. An $(n,x,y)$-win is minimal if it has minimal length amongst all $(n,x,y)$-wins; let $a_n$ denote that minimal value (by symmetry, it is independent of $x,y$).

Here's what you have to prove by induction:

The set of $(n,1,3)$ wins of minimal length corresponds bijectively to the Cartesian product of set of minimal $(n-1,1,2)$ wins and the set of minimal $(n-1,2,3)$ wins. The bijection goes like this:

1. first choose a minimal $(n-1,1,2)$ win, and use it to move all but the largest piece from $T_1$ to $T_2$;
2. then move the largest piece from $T_1$ to $T_3$;
3. then choose a minimal $(n-1,2,3)$ win, and use it to move all of the pieces from $T_2$ to $T_3$.

Once this has been proved, it immediately follows that $a_n = 2 a_{n-1} + 1$, because every minimal $(n,1,3)$ win starts with $a_{n-1}$ moves, followed by $1$ move, followed by $a_{n-1}$ moves.

Answer 2

Yes, there is a bijective function that maps the state of the Tower of Hanoi problem to a binary representation, which in turn can be mapped to a decimal number. This function is used to solve the problem recursively and efficiently.

. .

To map the state of the Tower of Hanoi problem to a binary representation, we can represent each disk as a binary digit, with 1 representing the top disk and 0 representing the rest of the stack. For example, if we have a stack of 3 disks, with the largest disk on the bottom and the smallest on the top, we can represent the state of the stack as 111. We can then concatenate the binary representations of the three poles to form a single binary string. For example, if the stack is on the first pole, the second pole is empty, and the third pole has no disks, we can represent the state as 111000. This binary string can be converted to a decimal number using the standard binary-to-decimal conversion algorithm. The resulting decimal number uniquely represents the state of the Tower of Hanoi problem.

. .

The bijective function for the recurrence relation is based on the observation that the minimum number of moves required to move n disks from one pole to another can be expressed as 2^n - 1. Therefore, we can define a function f(n) that maps the decimal representation of the state of the Tower of Hanoi problem to the minimum number of moves required to move the disks from one pole to another. The inverse function f^-1(m) can be used to compute the binary representation of the state of the problem, given the minimum number of moves required to solve it.