Question

Suppose that $\mathit{f}\mathbf{\left(}\mathit{n}\mathbf{\right)}\mathbf{=}\mathit{f}\mathbf{(}\mathit{n}\mathbf{/}\mathbf{3}\mathbf{)}\mathbf{+}\mathbf{1}$when is a positive integer divisible by 3, and $\mathit{f}\mathbf{\left(}\mathbf{1}\mathbf{\right)}\mathbf{=}\mathbf{1}$. Find:

a)$\mathit{f}\mathbf{\left(}\mathbf{3}\mathbf{\right)}$.

b)$\mathit{f}\mathbf{\left(}\mathbf{27}\mathbf{\right)}$.

c)localid="1668607414775" $\mathit{f}\mathbf{\left(}\mathbf{729}\mathbf{\right)}$.

Short answer

The answers are given below;

(a)$f\left(3\right)=2$

(b)$f\left(27\right)=4$

(c)$f\left(729\right)=7$

Step-by-step solution

Recurrence Relation definition

A recurrence relation is an equation that recursively defines a sequence where the next term is a function of the previous terms: $\mathbf{\text{f(n) = a f(n / b) + c}}$

Apply Recurrence Relation

Given:

$$\begin{gathered} f\left(n\right)=f(n/3)+1 \\ f\left(1\right)=1 \end{gathered}$$

(a) Repeatedly apply the recurrence relation with $n=3$:

$$\begin{gathered} f\left(3\right)=f\left(1\right)+1 \\ f\left(1\right)=1 \\ f\left(3\right)=1+1 \\ f\left(3\right)=2 \end{gathered}$$

(b) Repeatedly apply the recurrence relation with $n=27$:

$$\begin{gathered} f\left(27\right)=f\left(9\right)+1 \\ f\left(27\right)=f\left(3\right)+2 \\ f\left(27\right)=f\left(1\right)+3 \\ f\left(1\right)=1 \\ f\left(27\right)=1+3 \\ f\left(27\right)=4 \end{gathered}$$

(c) Repeatedly apply the recurrence relation with $n=729$:

$$\begin{gathered} f\left(729\right)=f\left(243\right)+1 \\ f\left(729\right)=f\left(81\right)+2 \\ f\left(729\right)=f\left(27\right)+3 \\ f\left(729\right)=f\left(9\right)+4 \\ f\left(729\right)=f\left(3\right)+5 \\ f\left(729\right)=f\left(1\right)+6 \\ f\left(729\right)=1+6 \\ f\left(729\right)=7 \end{gathered}$$