# Does a bijective function exists behind every recurrence relation?

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..

• In what way is there a one-to-one correspondence involving $a_{n,m}$ when there are two paths leading to it ??
– user16034
Commented Mar 20, 2023 at 19:29
• A bijection is between two sets, which you don't make explicit.
– user16034
Commented Mar 20, 2023 at 19:31