0
$\begingroup$

I have a recursive formula of a method $f\left(a,b\right)$:

$f\left(a,b\right) = \begin{cases} f\left(a,\lfloor \frac{b}{2} \rfloor\right) \cdot f\left(a,b-\lfloor \frac{b}{2} \rfloor\right) & \text{if $b > 1$} \\ a & \text{if $b = 1$} \\ 0 & \text{if $b = 0$} \end{cases}$

with $a,b \in \mathbb{N}$ (including $0$).

By calculating a few examples, I found out that the function is the power function:

$f\left(a,b\right)=a^b$

How can I prove this? Thanks for your help.

Example

$ \begin{align} f\left(5,3\right) &= f\left(5,\lfloor \frac{3}{2} \rfloor \right) \cdot f\left(5,3-\lfloor \frac{3}{2} \rfloor \right) \\ &= f\left(5,1\right) \cdot f\left(5,2 \right) \\ &= f\left(5,1\right) \cdot f\left(5,\lfloor \frac{2}{2} \rfloor \right) \cdot f\left(5,2-\lfloor \frac{2}{2} \rfloor \right) \\ &= f\left(5,1\right) \cdot f\left(5,1\right) \cdot f\left(5,1\right) \\ &= f^3\left(5,1\right) \\ &= 5^3 \end{align} $

$\endgroup$
1
  • $\begingroup$ It can't be, as $f(a, 0) = 0$, while $a^0 = 1$. $\endgroup$ Commented Aug 14, 2019 at 12:37

1 Answer 1

Reset to default
1
$\begingroup$

Prove it using strong induction.

Assume that $f(a, c) =a^c $ for all $c < b$.

Using this, prove that $f(a, b) = a^b$.

This should not be too hard.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.