>< 3 Times Function Makes a Composition! ><

Algebra Level 5

A function defined from the positive integers to the positive integers satisfies $0 < f(a) < f(b)$ for all $a < b$ . In addition, this function $f$ satisfies $f(f(x))=3x$ . Find $f(2015)+f(2014)+f(2013)-3 f(2012) .$

The answer is 18.

3 solutions

Mat Baluch
Jan 8, 2015

We first remark that the sought expression is:

S = {f(2015)-f(2012)} + {f(2014) - f(2012)} + {f(2013) - f(2012)}

Which leads to understand what is the "slope" of f.

A first important remark is that the local slope belongs to {1,2,3}: for a>0:

3 = f(f(a+1 - a)) >= f(a+1-a) >= f(a+1) - f(a) since f(n) >= n (which is direct with f strict growth) hence f(a+1)-f(a) (>0) belongs to {1,2,3}.

We then at patterns for the first integers, it appears:

since f(f(1)) = 3, and f(n) >= n, f(1) <= 3; f(1) = 1 leads to a contradiction ( if so f(f(1)) = f(1) = 1), so does f(1) = 3 ( if so f(3) = 3 which contradicts strict growth of f).

Hence f(1) = 2

f(f(1)) = 3x2 = f(2)

Hence f(2) = 6

f(f(2)) = 3x6 = f(6)

Hence f(6) = 18 ....

By recursion we can show that, for n>=0: f(3^n) = 2x3^n f(2x3^n) = 3^(n+1)

and then remark that:

in an interval [3^n, 2x3^n], f has a slope of 1 (f(p)-f(q) = p-q for all integers in this interval), since: f(2x3^n) - f(3^n) = 3^(n+1) - 2x3^n = 3^n = (2x3^n) - (3^n)
in an interval [2x3^n, 3^(n+1)], f has a slope of 3 (f(p)-f(q) = 3x(p-q) for all integers in this interval), since: f(3^(n+1)) - f(2x3^n) = 2x3^(n+1) - 3^(n+1) = 3^(n+1) = 3x { (3^(n+1)) - (2x3^n)} and the local slope can not exceed 3: f(p+1)-f(p) <= 3

Finally, 2012, 2013, 2014, 2015 all lie in the second type of intervall, meaning that

f(2015) - f(2012) = 3x3

f(2014) - f(2012) = 3x2

f(2013) - f(2012) = 3

S = 18

Shamik Banerjee
Jan 18, 2014

f(f(x)) = 3x Putting x = 1, we get f(f(1)) = 3. Say, f(1) = m => f(m) = 3.
The only satisfactory value is m = 2. Thus, we get f(1) = 2, f(2) = 3. Putting x = 2, we get f(f(2)) = 6 => f(3) = 6.

After analyzing the function f(f(x)) = 3, it has been found that f(3n)=3 * f(n), f(3n + 1) = 2 * f(n) + f(n+1), f(3n + 2) = f(n) + 2 * f(n+1) for n>0.

f(2015) + f(2014) + f(2013) - 3 * f(2012) = f(3 * 671 + 2) + f(3 * 671 + 1) + f(3 * 671) - 3 * f(3 * 670 + 2) = f(671) + 2 * f(672) + 2 * f(671) + f(672) + 3 * f(671) - 3 * f(670) - 6 * f(671) = 3 * {f(672) - f(670)} = 3 * {f(3 * 224) - f(3 * 223 + 1)} = 3 * {3 * f(224) - 2 * f(223) - f(224)} = 6 * {f(224) - f(223)} = 6 * {f(3 * 74 + 2) - f(3 * 74 + 1)} = 6 * {f(74) + 2 * f(75) - 2 * f(74) - f(75)} = 6 * {f(75) - f(74)} = 6 * {f(3 * 25) - f(3 * 24 + 2)} = 6 * {3 * f(25) - f(24) - 2 * f(25)} = 6 * {f(25) - f(24)} = 6 * {f(3 * 8 + 1) - f(3 * 8)} = 6 * {2 * f(8) + f(9) - 3 * f(8)} = 6 * {f(9) - f(8)} = 6 * {f(3 * 3) - f(3 * 2 + 2)} = 6 * {3 * f(3) - f(2) - 2f(3)} = 6 * {f(3) - f(2)} = 6 * (6 - 3) = 18

I m not getting ur solution, will u please format it again.

Suyog Gadhave - 7 years, 4 months ago

how did u find out the "analyzing the function f(f(x)) = 3, it has been found that $f(3n)=3 * f(n), f(3n + 1) = 2 * f(n) + f(n+1), f(3n + 2) = f(n) + 2 * f(n+1)$ for $n>0$ ." ???

Is there any proof to the above?

Happy Melodies - 6 years, 5 months ago

Bob Kadylo
Jun 6, 2018

For a very interesting way to find function values using Base 3: see here

>< 3 Times Function Makes a Composition! ><

The answer is 18.

3 solutions

0 pending reports