Functional Equations in Math
Functional equations involve functions referencing themselves, requiring specific techniques for solution. Explore types of questions and key concepts in this area of mathematics.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Topic 7: Functional Equations Dr J Frost (jfrost@tiffin.kingston.sch.uk) www.drfrostmaths.com Last modified: 31st August 2015
Slide Guidance Key to question types: SMC Senior Maths Challenge Uni University Interview Questions used in university interviews (possibly Oxbridge). The level, 1 being the easiest, 5 the hardest, will be indicated. BMO British Maths Olympiad Frost A Frosty Special Questions from the deep dark recesses of my head. Those with high scores in the SMC qualify for the BMO Round 1. The top hundred students from this go through to BMO Round 2. Questions in these slides will have their round indicated. Classic Classic Well known problems in maths. MAT Maths Aptitude Test STEP STEP Exam Admissions test for those applying for Maths and/or Computer Science at Oxford University. Exam used as a condition for offers to universities such as Cambridge and Bath.
Slide Guidance Any box with a ? can be clicked to reveal the answer (this works particularly well with interactive whiteboards!). Make sure you re viewing the slides in slideshow mode. ? For multiple choice questions (e.g. SMC), click your choice to reveal the answer (try below!) Question: The capital of Spain is: A: London B: Paris C: Madrid
What are functional equations? ? ? = ? + 1 You should be familiar with the concept of a function: something which takes an input and produces an output. Now suppose we used this function to form an equation: ? ? ? ? = ? + 1 ? + 1 = ?? + ? + ? + 1 = ? ?? + ? ? + ? ? 2 ? ? ?
What are functional equations? ? ? ? ? = ? ?? + ? ? + ? ? 2 We ve now defined the function in terms of itself rather than just in terms of its input. When a function makes reference to itself, it s known as a functional equation. We ve established the above is true when ? ? = ? + 1. But what if we just had the above equation, and didn t know what the original function was. How could we work them out? Trial and error? And even if we guessed ? ? = ? + 1 and found it satisfied the functional equation, how would we know (i.e. how would we have proved) that this is the only possible function that satisfies it?
Types of questions The types of questions you might see on functional equations often fall into one of the two categories: Given functional equation(s), what are the possible original (i.e. explicit ) functions? 1 Given functional equation(s), can we work out a particular output of the function, e.g. what ? 50 is, without even having the explicit definition of the function? 2
Terminology What is the name of these functions? ? ? = ? (where ? is a constant) Constant Function ? ? ? = ? Identity Function ? Convention: We often use ? and ? for real numbered variables and ? for integer variables.
Strategy #1 Specialising Find all functions ? that satisfy ? ?? = ? ? + ?(?) for all real ?,?. The key is to specialise, that is, trying some specific values of ? and ? and see if they yield any clues about the function. e.g. Let ? = 0. What can we conclude? Then: ? 0 = ? ? + ?(0) ? ? = ? 0 ? 0 = 0 ? Thus ? ? = 0 for all values of ?.
Strategy #1 Specialising Find all functions ? that satisfy ? ? + ?2= ? ?2+ ? ?2 for all real ?,?. What would be a good starting point? Let ? = ? = ?. Then ? ??= ? ??+ ? ??. Thus ? ??= ? and so ? ? = ?. ? Now given that we know what ?(0) is, is there any way we can set ? and ? such that we can relate ?(0) and ?(? + ?)? Let ? = ?. Then: ? ??= ? ??+ ? ?? ? ??+ ? ??= ? ? Thinking about the Algebra slides, what must we conclude? Squared terms must be positive, and the sum is 0, so ? ??= ?, and thus ? ? = ? for all ?. ?
But this approach doesnt always work Now let s return to the previous functional equation, but restrict the domain a little more Find all functions ? that satisfy ? ?? = ? ? + ?(?) for all positive real ?,?. We could try ? = 1. This would allow us to conclude that: ? ? = ? ? + ?(?) Thus ? ? = ? ? But it would be difficult to proceed further, because we re now no longer allowed to use ? = 0 or ? = 0, since 0 is outside the domain of the function (i.e. positive reals) But since we know ? 1 = 0. Could we let ? and ? be something such that we can relate ?(1) and ?(??)? Let ? =? ?, then: ? ? ? ? = ? ? + ? ? ? ? ? ? = ?
But this approach doesnt always work Find all functions ? that satisfy ? ?? = ? ? + ?(?) for all positive real ?,?. We ve managed to establish: ? ? = ? ? ? ? ? = ? Proceeding further by specialising won t get us far. For those who ve done bits of C2, could you guess a function that satisfies the above? ? ? = ????? + ? (where ? and ? are constants) ? Proving this is the onlyfamily of solutions* though isn t possible using this technique. One method of proving this is using partial differentiation, which is covered at the end of these slides. * I say family of solutions because we can choose different values for constants ? and ?, but the underlying form of the function remains the same.
Olympiad Example Question: Find all functions ?, defined on the real numbers and taking real values, which satisfy the equation ? ? ? ? = ? ? + ? + ??for all real values ? and ?. Full Solution: See if you can work out these on your own using the specialisation method we ve seen: Using ? = 0, ? ? ? 0 = ?(?), thus ? 0 = 1. We can use ? = ? so that ? ? + ? = ? 0 = 1. This gives us ? ? ? ? = 1 ?2 Now if ? = 1, then ? 1 ? 1 = 0 Thus ? 1 = 0 or ? 1 = 0 ? ? 0 = 1 ? 1 ?? ? 1 = 0 ? Case 1: ? 1 = 0. Then letting ? = 1 so that we get rid of the ? ? : 0 = ? ? + 1 + ? ? ? + 1 = ? Which is equivalent to ? ? = ? 1 = 1 ? ? BMO Case 2: ? 1 = 0. Then letting ? = 1 for the same reason: 0 = ? ? 1 ? ? ? 1 = ? ? ? = ? + 1 Round 2 Round 1
Summary so far Make clever substitutions. Common ones are: ? = ? which lets us get rid of the ?. Although if ?(?) is in the functional equation, then we obviously need to know what ?(1) is. ? = ?or ? = ? = ? Often helps us determine ?(0), or simplify our functional equation. ? =? ? ? = ? A good idea when ? ? + ? is in our functional equation. But we d need to know what ?(0) is. A good idea when ?(??) is in our functional equation. But we d need to know what ?(1) is. It often helps to try and establish what ?(0) and ?(1) is via substitution, in order that we can make further substitutions!
Strategy #2 Exploiting Self-Inverses A function is self-inverse, when applying it twice gets you back to the original input, i.e. ? ? ? = ? Examples: ? ? ? =? ? ? = ? ? ? ? = ? ? ? ?
Strategy #2 Exploiting Self-Inverses Find all functions ? such that: 1 ? ? ? + 2? = 2? Now since 1 sensible to yield two equations? ? is a self-inverse function, what two substitutions might be Letting ? = ?: 1 ? ? ? + 2? = 2? Letting ? =? ?: + 2? ? =2 ? 1 ? ? ? ? ? =4 2?2 We now have simultaneous equations. We could eliminate ? ? by appropriate elimination. This gives us our solution: 3?? 1
Strategy #3 Induction Sometimes we can spot the function that satisfies the functional equations: For all integers ?: ? ? + 1 = ? ? + 2 ? 1 = 1 What is ?? ? ? = ?? ? ? Just looking at the functional equations above, we can see that we have the arithmetic sequence 1, 3, 5, 7, as ? increases, which obviously has the formula ? ? = 2? 1 We could formally show this by induction. Suppose ? ? = 2? 1 is true for ?. Then in our inductive step: ? ? + 1 = 2 ? + 1 1 = 2? 1 + 2 = ? ? + 2 And in the base case, where ? = 1, we have that ? 1 = 1.
Strategy #4 Using a function substitution We ve so far approached functional equations by substituting the input, e.g. ? = 0 or ? = ?. But sometimes we must want to replace the function with a completely different one to make the functional equation easier to solve. There will sometimes be clues in the equation with regards to the substitution we can make. The function ? is defined on the set of positive integers by ? 1 = 1, ? 2? = 2? ? and ?? 2? + 1 = 2? + 1 ? ? + ? for all ? 1. (i) Prove that ?(?) is always an integer. (ii) Notice that the 2? + 1 appears both within the function brackets and outside (as does ?). Can you think therefore what might be a sensible substitution? ? ? =? ? BMO Round 2 ?? Round 1
Strategy #4 Using a function substitution The function ? is defined on the set of positive integers by ? 1 = 1, ? 2? = 2? ? and ?? 2? + 1 = 2? + 1 ? ? + ? for all ? 1. (i) Prove that ?(?) is always an integer. (ii) Notice also that the arguments of ?are 2? and 2? + 1. What s significant about using these as inputs? They represent even and odd integers. ? This suggests we should do the same for ? ? . Use the definition of ? above to simplify these: ? 2? =? 2? =2? ? =? ? ? = ? ? 2? 2? 2? + 1 ? ? + ? ? 2? + 1 ? ? ? 2? + 1 =? 2? + 1 =?? 2? + 1 ? 2? + 1 =? ? = + 1 = ? ? + 1 2? + 1 ? ? 1 =? 1 =1 1= 1 1 Wow, that substitution really did give us simpler functional equations!
Strategy #4 Using a function substitution The function ? is defined on the set of positive integers by ? 1 = 1, ? 2? = 2? ? and ?? 2? + 1 = 2? + 1 ? ? + ? for all ? 1. (i) Prove that ?(?) is always an integer. (ii) ? 2? = ? ? ? 2? + 1 = ? ? + 1 ? 1 = 1 We ve got to prove ? ? is always an integer. But since ? ? = ? ? ? , it s sufficient to prove ? ? is an integer, as ? ? will then be. I smell induction! We can use the second type of induction: supposing that ?(1) up to ? ? are all integers, and thus that ? ? + 1 is: Base case: ? 1 = 1, and 1 is an integer. Inductive case: Suppose ?(1) to ?(?) are integers. Then if ? + 1 is even, ? + 1 = 2?. Now ? 2? = ?(?), and ? ?, so by induction, ?(?) is an integer. Thus ? ? + 1 is an integer. If ? + 1 is odd, then ? + 1 = 2? + 1. Now ? 2? + 1 = ? ? + 1. Again, ? ? so ?(?) is an integer, and clearly ? ? + 1 then is. ?
Strategy #5 Using a different number base The function ? is defined on the set of positive integers by ? 1 = 1, ? 2? = 2? ? and ?? 2? + 1 = 2? + 1 ? ? + ? for all ? 1. (i) Prove that ?(?) is always an integer. (ii) One more exotic approach (which I won t cover in detail here), which particularly seems to crop up in more difficult questions, is to define a new function in terms of the binary representation of the input. e.g. 5 = 1012 This is often a viable approach when we find ? 2? + 1 and ? 2? defined in terms of ?(?). Suppose we let ? ? = the count of 1s in the binary representation of ? (e.g. ? 5 = ? 1012 = 2) and ? ? = ? ?(?), then it turns out that we find that ? ? satisfies all the functional equations stated in the question! (I ll leave this as an exercise ) Because the count of ones is always an integer, then ?(?) is always an integer as required by the question. The challenge then is to find a function in terms of the binary representation of the input that will satisfy the functional equations given. Note that this approach isn t really applicable for types of questions where we re asked to find all ? which satisfies the functional equations, because any valid binary function we found is just one solution: it doesn t prove we can t find others.
Finding specific outputs Sometimes, given some functional equations, we don t actually need to work out what ?(?) is. We might just be required to find the possible values of ?(100) . Oxford interview question (candidates were given a day in advance) Let ?(?) be a function where ? 0,? (i.e. the domain is non-negative integers) and ? ? 0 Suppose the three functional equations hold: i) ii) ? 10 = 1 iii) ? ? = 0 if ? ends in a 3. ? ?? = ? ? + ? ? Question (a): Find ?(??). Hint: 17 ends with a 7. What could we do with 17 to make it end with a 3? You don t need condition (ii) for this question.
Finding specific outputs Oxford interview question (candidates were given a day in advance) i) ii) ? 10 = 1 iii) ? ? = 0 if ? ends in a 3. ? ?? = ? ? + ? ? Question (a): Find ?(??). A solution Note that 17 9 = 153. We multiplied by 9 to get a number ending in 3. i.e. ? 17 9 = 0. At this point it seems sensible to use (i) since we have a product inside the function brackets. From (i) we have that ? 3? = ? 3 + ? ? = 0 + ? ? = ?(?) Thus ? 17 9 = ? 17 3 = ? 17 = 0
Finding specific outputs Oxford interview question (candidates were given a day in advance) Let ?(?) be a function where ? 0,? (i.e. the domain is non-negative integers) and ? ? 0 Suppose the three functional equations hold: i) ii) ? 10 = 1 iii) ? ? = 0 if ? ends in a 3. ? ?? = ? ? + ? ? Question (b): What are the possible values of ? ??? ? By using (i), ? 500 = ? 10 + ? 10 + ? 5 = 2 + ?(5) Note that ? 10 = 1 = ? 2 + ?(5). But since ? ? 0 for all ?, ? 5 must be 0 or 1. ? Thus ?(500) could either be 2 or 3.
Common functional equations to remember ? ? = ?log ? + ? ? ?? = ? ? + ?(?) When domain: ? > 0 ? ? = ?? ? ? + ? = ? ? ?(?) For integers/rationals: ? ? = ?? But additional more complicated solutions for reals. ? ? + ? = ? ? + ?(?) Known as Cauchy s Functional Equation
Cauchys Functional Equation ? ? + ? = ? ? + ?(?) Solving this functional equation has been used as a topic for discussion in an Oxford maths interview. Prove that ? ? = ?? over the integers. Let ? = ?: ? ? + ? = ? ? + ?(?) ? ?? = ??(?) But we could keep adding extra ? s: ? ? + ? + ? = ?( ? + ? + ?) = ? 2? + ?(?) ? ?? = 2? ? + ? ? = ??(?) By continuing this ( inductively ) we have that: ? ?? = ??(?) where ? is an integer, but ? is any real (? is at the moment restricted to integers, because in the workings above we had ?lots of ?, and we can t have a fractional number of things)
Cauchys Functional Equation Prove that ? ? = ?? over the integers. ? ?? = ??(?) where ? is an integer, but ? is any real So far: Let ? 1 = ? and ? = 1 Then ? ? = ?? i.e. We ve proved it over the integers (since ? is an integer). Prove that ? ? = ?? over the rational numbers. We know ? ? = ?? when ? is an integer. Observe that ? = ?? ? where ? is an integer. Then ?? = ? ? = ? ?? ? ? = ? ? ? which we were allowed to do because ? is an integer and we know that ? ?? = ?? ? when ? is an integer, as at the top of the slide) ? ? =?? ?, i.e. ? ? = ?? where ? =? Thus dividing by ?: ? ?, i.e. ? is rational.
Cauchys Functional Equation Prove that ? ? = ?? over the reals if ? is an increasing function. Suppose we wanted to show that ? ? = ??. If ? is increasing, then ? < ? if and only if ? ? < ?(?). Then we can bound the value between two rationals: because ? is increasing 3.14 < ? < 3.15 ? 3.14 < ? ? < ?(3.15) But since we showed that ? ? = ?? for rational ?: 3.14? < ? ? < 3.15? We could make these bounds arbitrarily tighter: 3.1415? < ? ? < 3.1416? Thus in the limit, ? ? = ??
Topic 8 Functional Equations Epilogue A proof using partial differentiation that the family of solutions to ? ?? = ? ? + ?(?) is ? ? = ?log ? + ?.
Proof of solutions ? to ? ?? = ? ? + ? ? We want to prove that if: ? ?? = ? ? + ? ? then when ? > 0: ? ? = ?log ? + ? To do so, we can use partial differentiation. Here s a very quick intro: (but I m assuming knowledge of the chain rule and product rule for differentiation, which is covered in the C3 A Level module)
Partial Differentiation By the chain rule, and conventional differentiation, we have for example: ? ?? ?? = ??? ??+ ? But in partial differentiation, all variables except the ones we re differentiating are treated as constants. Thus: ? ?? ?? = ? Notice the curly d.
Proof of solutions ? to ? ?? = ? ? + ? ? ? ?? = ? ? + ? ? ? ? ?? = ? (?) (1) Partially differentiating (1) with respect to ?. Note that ?(?)disappears because it doesn t use ?, so everything is a constant. (2) 1 ? ? 1 = ? ? ? ? =? Letting ? =1 (3) ? (4) Letting ? = ? 1 and rearranging. ? ? ? = ?ln? + ? (5) Integrating w.r.t. ? for ? > 0 This therefore provides us with an alternative way to solve functional equations: by partially differentiating.
