Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
3  
Multiplication? –  André Nicolas Feb 28 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 at 0:52
    
@ElThor My mistake. I need to take a closer look. –  Mike Feb 28 at 0:59
    
Apart from the switch of order, it is the standard recursive definition of multiplication. –  André Nicolas Feb 28 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 at 1:24

1 Answer 1

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|improve this answer

Your Answer

 
discard

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.