Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!


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?

share|cite|improve this question
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
up vote 2 down vote accepted

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.