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

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.