Elementary Functions Name: f(a,b) = f(b,a-1)+b

Question

I am quite simply looking for a function that I forgot about from way back when. I am positive I learned this at some point in grade school, but I just can't remember what it is called!

The function in question is:

 if a = 0: f(a,b) = 0
 if a ≠ 0: f(a,b) = f(b,a – 1) + b

I am hoping that someone can remember what this is called! Thanks in advance!

EDIT

I am providing the simple code that I came up with that runs in Python. It does seem to be multiplication:

 def f(a,b,string):
     if (a==0):
         print (string)
         return 0
     if (a!=0):
         string += ( " + "+str(b) )
         return (f(b,a-1,string)+b) 

NEXT QUESTION: Is there a proof for this anywhere?

Answer 1

Multiplication it is! We prove this by induction on $a$ and $b$.

• Base: $f(0,b)=0$ by definition and $f(a,0)=f(0,a-1)+0=0$
• Induction hypothesis: $\forall n<a$ and $\forall m<b$, $f(n,m)=f(m,n)=m\cdot n$
• Induction step: We must prove that $f(a,b)=f(b,a)=a\cdot b$. We have \begin{align} f(a,b)&=f(b,a-1)+b\\ &=f(a-1,b-1)+a+b-1 \end{align} But by induction hypothesis, we have $f(a-1,b-1)=(a-1)(b-1)$ and $f(a-1,b-1)=f(b-1,a-1)$. Then $$f(a,b)=(a-1)(b-1)+a+b-1=ab$$ and \begin{align} f(b,a)&=f(b-1,a-1)+a+b-1\\ &=f(a-1,b-1)+a+b-1\\ &=f(a,b) \end{align}

In fact, we could restrict the induction hypothesis to only $a-1$ and $b-1$ instead of all integers smaller than $a$ and $b$.