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

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?

-
Multiplication? – André Nicolas Feb 28 '14 at 0:44
With f(7,5), I return did return 35. Sorry for any confusion. I'm working on making a quick little program and proof for it now. I can't remember ever seeing multiplication this way! – T.Woody Feb 28 '14 at 0:52
@ElThor My mistake. I need to take a closer look. – Mike Feb 28 '14 at 0:59
Apart from the switch of order, it is the standard recursive definition of multiplication. – André Nicolas Feb 28 '14 at 1:09
Yeah, it's the switch that makes it non-obvious. It's like counting the number of elements in a grid of $a$ rows of $b$ elements by using a spiral pattern to cross out each element. – Mike Feb 28 '14 at 1:24

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