Grades 11-12 Video Solutions 2013-Levels 11&12 Video Solutions 2013 problem25

Video Transcription

Question number 25.  Let f mapping the non-negative integers to the non-negative integers be the function defined by f of n is equal to n divided by 2 if n is an even natural number  and f of n is equal to n minus 1 divided by 2 if n is an odd natural number.  Now for k, a positive integer, f to the power k of n denotes the number represented by the expression shown here.  Where the symbol f appears k times. So this is nothing other than the k-fold composition of the function f with itself evaluated at n. Now we have  to compute the number of solutions of the equation f  to the power 2013 of n equal to 1.  So we have to at some point compose the function n with itself 2013 times and then evaluate that at n. So let's study the simpler case where we just have f  to the power 1 or f of n is equal to 1.  And this has exactly 2 solutions.  What we do is we write n symbolically as the inverse of f applied to 1 and we see that if we choose n to be 2, then dividing 2 by 2 gives us 1 or if we choose n to be 3,  subtracting 1 from 3 dividing by 2 after that also gives us 1.  So we can compute in general the inverse of f  for any integer input k and we see that according to our rules, either this is given by 2k for k even or 2k plus 1 for k odd.  And so the inverse here of f is not a function but no matter we can use it to solve our problem.  Let's do one more case.  f of n equal to 1 happens provided that f of n is equal to the f inverse of 1 which we already calculated as 2 or 3 and then finally n would be equal to f inverse applied  to f inverse of 1 so that's f inverse of 2,  f inverse of 3 and both of these have 2 values, 4 and 5  for the inverse of 2 and 6 and 7 for the inverse of 3. And then we can keep going like that. The inverse values of 4 would be 8 and 9,  for 5 we would get 10 and 11, for 6, 12 and 13,  for 7, 14 and 15 and so forth. And we see that at each step we have a multiple of 2  and in general after some sort of inductive argument, we can say that by induction the number of solutions here is given by 2 to the power k. Hence 2 to the power 2013 solutions  to the functional equation 2 to the 2000,  f to the 2013 of n equal to 1 and so that's the answer here d.

Video Summary

The problem involves finding the number of solutions for the function \( f^k(n) = 1 \), where \( f \) applies a rule based on whether \( n \) is even or odd. Exploring \( f^1(n) = 1 \) reveals 2 solutions: \( n = 2 \) or \( n = 3 \). Extending this, we observe that each step doubles the number of solutions, establishing a pattern. By induction, the number of solutions for \( f^{2013}(n) = 1 \) is \( 2^{2013} \). Thus, the number of solutions for the equation \( f^{2013}(n) = 1 \) is \( 2^{2013} \).

Keywords

function solutions

induction pattern

even odd rule

exponential growth

mathematical problem