The Binary Recurrence Relation and Proof by Structural Induction

Question

A two-dimensional function f, whose domain in N x N is defined by,

$u(x) = \begin{cases} 2b & \text{if } a = 0 \\ 0 & \text{if } a \geq 1 \ and \ b = 0 \\ 2 & \text{if } a \geq 1 \ and \ b = 1 \\ f(a-1, f(a, b-1)) & \text{if } a \geq 1 \ and \ b \geq 2 \end{cases}$

i) Can $f(a, 2) = 4$ for a $\geq$ 1 be established using induction?
ii) Evaluate $f(2, 3)$ and $f(3, 3)$ ?

Solution

==================================================================================================

Ans i: Proof by Induction

To be proven: $f(a, 2) = 4$ for $a \geq 1$

Let’s use structural induction to prove this result as it is a recursion problem.

Basis Step:

$f(1, 0) = 0, f(1, 1) = 2$ (from f(a, b)).
$f(1, 2)$ is P(1).
$f(1, 2) = f(a-1, f(a, b-1)) = f(0, f(1, 1)) = f(0, 2) = 2 * 2 = 4$

Thus, P(1) holds and basis step proved.

Recursive Step:

If we assume that P(k) holds for all numbers till k & $a \geq 1$ ; this means that $F(k, 2) = 4 \ \forall \ 1 \leq a \leq k$ .

We need to prove if P(k+1) holds.

P(k+1) => F(k+1, 2) = 4

$\begin{align*} \left LHS = F(k+1, 2) = f(a-1, f(a, b-1)) = f(k, f(k, 1)) = f(k, 2) \end{align*}$

$\begin{align*} \left LHS = 4 \ (from \ inductive \ hypothesis) \end{align*}$

Thus, the proof holds for P(k+1).

Ans ii: Evaluate $f(2, 3)$ and $f(3, 3)$

$f(2, 3) => a \geq 1 \ and \ b \geq 2$

$\begin{align*} \left f(2, 3) = f(a-1, f(a, b-1)) = f(1, f(2, 2)) = f(1, f(2-1, f(2, 1))) = f(1, f(1, f(2, 1))) \end{align*}$

$\begin{align*} \left = f(1, f(1, 2)) = f(1, f(1-1, f(1, 1))) = f(1, f(0, f(1, 1))) = f(1, f(0, 2)) = f(1, 4) \end{align*}$

$\begin{align*} \left = f(1-1, f(1, 3)) = f(0, f(1-1, f(1, 2))) = f(0, f(0, f(1-1, f(1, 1)))) \end{align*}$

$\begin{align*} \left = f(0, f(0, f(0, 2))) = f(0, f(0, 4)) = f(0, 8) = 16 \end{align*}$

Thus, $f(2, 3) = 2^4$

$f(3, 3) => a \geq 1 \ and \ b \geq 2$

$\begin{align*} \left f(3, 3) = f(a-1, f(a, b-1)) = f(2, f(3, 2)) = f(2, f(2, f(3, 1))) = f(2, f(2, 2))) \end{align*}$

$\begin{align*} \left = f(2, f(1, f(2, 1))) = f(2, f(1, 2))) = f(2, f(0, f(1, 1))) = f(2, f(0, 2)) = f(2, 4) \end{align*}$

$\begin{align*} \left = f(1, f(2, 3)) = f(1, f(1, f(2, 2))) = f(1, f(1, f(1, f(2, 1)))) \end{align*}$

$\begin{align*} \left = f(1, f(1, f(1, 2))) = f(1, f(1, f(0, f(1, 1)))) = f(1, f(1, f(0, 2))) = f(1, f(1, 4)) \end{align*}$

$\begin{align*} \left = f(1, f(0, f(1, 3))) = f(1, f(0, f(0, f(1, 2)))) = f(1, f(0, f(0, f(0, f(1, 1))))) \end{align*}$

$\begin{align*} \left = f(1, f(0, f(0, f(0, 2)))) = f(1, f(0, f(0, 4))) = f(1, f(0, 8)) = f(1, 16) \end{align*}$

$\begin{align*} \left = f(0, f(1, 15)) = f(1, 16) = f(0, f(0, f(1, 14))) \end{align*}$

This will go on till b becomes 1. The term will be $2^1, 2^2, 2^3, .... , 2^{16}$ .

Thus, $f(3, 3) = 2^{16}$

Question

Solution

Ans i: Proof by Induction

Ans ii: Evaluate $f(2, 3)$ and $f(3, 3)$

Subscribe to Ehan Ghalib!

Leave a Reply Cancel Reply

Question

Solution

Ans i: Proof by Induction

Ans ii: Evaluate and

Subscribe to Ehan Ghalib!

Leave a Reply Cancel Reply

Subscribe to Ehan Ghalib

Ans ii: Evaluate $f(2, 3)$ and $f(3, 3)$