How can I recursively define functions of more than one variable? If I want to recursively define a

Emanuel Keith 2022-06-24 Answered
How can I recursively define functions of more than one variable?
If I want to recursively define a function f : N N , I can follow the following simple schema:
1. Define f(0) explicitly.
2. For each n 0, define f ( n + 1 ) in terms of f(n).
This ensures that each natural number has a unique image under f. Now suppose I want to recursively define a two-variable function g : N × N N . For example, maybe I want to define binomial coefficients, or stirling numbers, or something. Is there an analogous schema I can use?
Note: I'm very new to math, so if you could be as explicit as possible, I would really appreciate it!
You can still ask an expert for help

Want to know more about Discrete math?

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

Solve your problem for the price of one coffee

  • Available 24/7
  • Math expert for every subject
  • Pay only if we can solve it
Ask Question

Answers (2)

humbast2
Answered 2022-06-25 Author has 21 answers
Step 1
You’ve discussed the most basic recursion principle, which states, in more formal terms,
Suppose a A, and suppose g : A A. There is a unique function f : N A such that f ( 0 ) = a and such that for all n, f ( n + 1 ) = g ( f ( n ) ).
In other words, if we define f(0) and then define f ( n + 1 ) in terms of f(n), we’ve defined f.
We can define more general functions in many ways, all derived from this schema. Here’s an illustrative example.
Step 2
Let A = N N . Let a A be defined by a ( 0 ) = 1 and a ( n + 1 ) = 0. Given x A, define g(x) by g ( x ) ( 0 ) = 1 and g ( x ) ( n + 1 ) = x ( n ) + x ( n + 1 ). Then g : A A.
Take f : N A such that f ( 0 ) = a and f ( n + 1 ) = g ( f ( n ) ). Then it turns out that ( n m ) = f ( n ) ( m ). For we see that ( n k ) = ( n 1 k 1 ) + ( n k ) whenever n , k > 0, and the base cases also match up.
Did you like this example?
Subscribe for all access
Llubanipo
Answered 2022-06-26 Author has 9 answers
Step 1
Yes. Again, you need
- one or more "recurrence relation", connecting some term to other terms,
- one or more "initial values", giving explicitly values for certain terms.
For example, the binomial coefficients can be defined by:
- b ( n , n ) = 1 for all n
- b ( n , 0 ) = 1 for all n
- b ( n , k ) = b ( n 1 , k 1 ) + b ( n 1 , k ) for 0 < k < n.
Step 2
Another scheme that works is:
- b ( 0 , 0 ) = 1
- b ( 0 , k ) = 0 for k 0
- b ( n , k ) = b ( n 1 , k 1 ) + b ( n 1 , k ) for all n > 0.
Did you like this example?
Subscribe for all access

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

You might be interested in

asked 2021-07-28

Let A, B, and C be sets. Show that (AB)C=(AC)(BC)
image

asked 2021-08-02

Suppose that A is the set of sophomores at your school and B is the set of students taking discrete mathematics at your school. Express each of these sets in terms of A and B. 
a) the set of sophomores taking discrete mathematics in your school 
b) the set of sophomores at your school who are not taking discrete mathematics 
c) the set of students at your school who either are sophomores or are taking discrete mathematics 
Use these symbols: 

asked 2021-08-15
How many elements are in the set { 0, { { 0 } }?
asked 2020-11-09
Use proof by Contradiction to prove that the sum of an irrational number and a rational number is irrational.
asked 2022-06-21
How many ways we can load 100 indistinguishable boxes into 3 cars A,B,C,if every car can be loaded with 20 to 40 boxes?
asked 2022-09-04
On each of the 22 work days in a particular month, every employee of a start-up venture was sent a company communication. If a total of 4730 company communications were sent, how many employees does the company have, assuming that no staffing changes were made that month?
From the Discrete math book :
If the finite set A is the union of n pairwise disjoint subsets each with d elements, then n = | A | / d
Using this formula from the book, I calculated this to be 4730 / 22 = 215
Can you please confirm if this is correct and if my understanding is right, because the book mentions this to be a hard problem and I am not sure if I am missing something?
asked 2022-07-17
I'm taking a discrete math course, and were on Bézout Coefficients right now. I kind of understand the algorithm, the generalization. However the example in the book is throwing me off.
The steps in the Euclidean algorithm to find gcd(101,4620) are:
4620 = 45 101 + 75 101 = 1 75 + 26 75 = 2 26 + 23 26 = 1 23 + 3 23 = 7 3 + 2 3 = 1 2 + 1 2 = 2 1
This I understand. Now to find the Bézout coefficients they follow these steps.
1 = 3 1 2 = 3 1 ( 23 7 3 ) = 1 23 + 8 3 = 1 23 + 8 ( 25 1 23 ) = 8 26 9 23 = 8 26 9 ( 75 2 26 ) = 0 75 + 26 26 = 0 75 + 26 ( 101 1 75 ) = 26 101 35 75 = 26 101 35 ( 4620 45 101 ) = 35 4620 + 1601 101
My problem is with the second line, where are they getting this +8 from? I've tried just about every algebraic trick I know, but I can't seem to find what they are actually doing.
I think I'm just missing some really simple algebra logic, but maybe I'm not understanding the steps to get Bézout coefficients?

New questions

Solve your problem for the price of one coffee

  • Available 24/7
  • Math expert for every subject
  • Pay only if we can solve it
Ask Question