+140 For all ordered pairs of positive integers (x,y) we define f(x,y) as follows:
(a) \(f(x,1) = x.\)
(b) if \(f(x,y) = 0\) if \(y > x.\)
(c) \(f(x + 1,y) = y[f(x,y) + f(x,y - 1)].\)
Compute f(5,5)
Hi sherwyo!
We are going to solve this by substituting the desired values in (c) I.e. we want f(x+1,y) = f(5,5) so x=4 and y=5:
Let x=4 and y=5
\(f(5,5)=5[f(4,5)+f(4,4)]\) by (c).
Then notice: \(f(4,5)=0 \space \space \text{As, y>x (5>4)}\) by (b).
So: \(f(5,5)=5f(4,4)\)
Now, we want to find \(f(4,4)\). We have to repeat the process!
let x=3, and y=4 in (c), to get f(4,4):
\(f(4,4)=4[0+f(3,3)]=4f(3,3)\)
Next, we need to find \(f(3,3)\):
Let x=2, and y=3:
\(f(3,3)=3f(2,2)\)
Now let's find \(f(2,2)\):
Let x=1, and y=2
\(f(2,2)=2f(1,1)=2(1)=2\) by (a).
So:
\(f(3,3)=3f(2,2)=3(2)=6\)
Hence,
\(f(4,4)=4f(3,3)=4(6)=24\)
Therefore,
\(f(5,5)=5f(4,4)=5(24)=120\)
Which is the answer.
Extra information: Notice, this function behaves exactly like \(n!\) for all integers n (Because it has the pattern 2,6,24,120 etc..)
But, our function is of two variables, namely x and y. But \(n!\) just relies on one variable.
But, notice, this pattern of results of \(f(x,y)\) occurs only when x=y. Therefore, \(f(x,y)=xPy\)
That is, the permutation function; which is defined as follows: \(nPk=\frac{n!}{(n-k)!}\)
So, in this case, we know x=y: \(xPy=xPx=\frac{x!}{0!}=x!\), the factorial function.
So, for example, if later asked what is \(f(200,200)\) we definitely will not keep doing what we did above till we reach 200. We will observe this pattern, then deduce it is the factorial function, and prove this result by induction and a simple substitution yields the answer.
I hope this helps :)!
