Limiting Recurrence

Calculus Level 3

Let f n ( x ) f_n(x) satisfy the recurrence relation f n ( x ) = f 1 ( f n 1 ( x ) ) f_n (x) =f_1 \big( f_{n-1} (x)\big) for n = 2 , 3 , 4 , n=2,3,4, \ldots and f 1 ( x ) = x 2 + 10 f_1 (x) = \dfrac x2 + 10 .

Evaluate lim n f ( x ) \displaystyle \lim_{n\to\infty} f(x) .


The answer is 20.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

3 solutions

Anubhav Tyagi
Dec 15, 2016

From given conditions, we write f 2 ( x ) = x 4 + 30 2 f 3 ( x ) = x 8 + 70 4 f 4 ( x ) = x 16 + 150 8 and from above we write the general term as: f n ( x ) = x 2 n + 10 + 20 + 40 + 80 + 160 + 320...... + 10 × 2 n 1 2 n 1 = x 2 n + 10 × ( 1 + 2 + 4 + 8 + 16 + 32...... + 2 n 1 ) 2 n 1 = x 2 n + 10 × ( 2 n 1 ) 2 n 1 = x 2 n + 20 10 2 n 1 lim n f ( x ) = 20 \begin{aligned} &f_2 (x) = \frac{x}{4} + \frac{30}{2} \\ &f_3 (x) = \frac{x}{8} + \frac{70}{4} \\ &f_4 (x) = \frac{x}{16} + \frac{150}{8} \\ &\text{and from above we write the general term as:} \\ &f_n (x) = \frac{x}{2^{n}} + \frac{10+20+40+80+160+320......+10\times 2^{n-1}}{2^{n-1}} \\ & = \frac{x}{2^{n}} + \frac{10\times(1+2+4+8+16+32......+ 2^{n-1})}{2^{n-1}}\\ & = \frac{x}{2^{n}} + \frac{10\times(2^{n} - 1 )}{2^{n-1}} \\ & = \frac{x}{2^{n}} + 20 - \frac{10}{2^{n-1}} \\ & \Rightarrow \lim_{n\to\infty} f(x) = 20 \end{aligned}

@Calvin Lin -check the solution and the problem

Anubhav Tyagi - 4 years, 6 months ago

Log in to reply

When you observe that there is a pattern, do you best to prove it instead of just describing it. You came really close to explaining why f n ( x ) f_n(x) must have that form.

Calvin Lin Staff - 4 years, 6 months ago

@Prakhar Bindal , @Rohit Kumar , @Josh Silverman - Try out the problem

Anubhav Tyagi - 4 years, 6 months ago

@Calvin Lin - why has the problem not been rated yet?

Anubhav Tyagi - 4 years, 6 months ago

Log in to reply

When you created the problem, you did not give it a seed level, so that delayed the start of the process. When we reviewed this problem, we gave it a seed level.

Calvin Lin Staff - 4 years, 5 months ago
Prakhar Bindal
Dec 15, 2016

i will share an easier approach

As n tends to infinity n tends to n-1

therefore

fn(x) = f1(fn(x))

substitute values

fn(x) = fn(x)/2+10

therefore fn(x) = 20

This is incorrect. You first need to show that the limit exists.

Pi Han Goh - 4 years, 6 months ago

Log in to reply

Fix x x and note that f n ( x ) = f 1 n ( x ) f_n(x) = f_1^n (x) where the exponent indicates the number of times f 1 f_1 is applied on x x .

As f 1 f_1 is contraction mapping, the existence of the limit (for every fixed x x ) follows by the Banach fixed point theorem.

A Former Brilliant Member - 4 years, 6 months ago

Log in to reply

These things tend to go over my mind :P @Deeparaj Bhat

Prakhar Bindal - 4 years, 6 months ago

I rather meant the proof of Banach fixed point theorem.

A Former Brilliant Member - 4 years, 6 months ago

Yep indeed i thought about this thing when i solved this problem . but as in the question no such option was available (limit does not exist then enter answer as.......) hence i thought of just solving it . now i am thinking of a way can you provide a way?

Prakhar Bindal - 4 years, 6 months ago

@Anubhav Tyagi

Prakhar Bindal - 4 years, 6 months ago

Log in to reply

Check out https://brilliant.org/problems/limits-part-1/

Anubhav Tyagi - 4 years, 6 months ago

I have some doubt about this approach though it leads to correct answer @Prakhar Bindal

Anubhav Tyagi - 4 years, 6 months ago

Log in to reply

nope its perfectly fine . this is one of the standard approach for dealing with such kind of summations

Prakhar Bindal - 4 years, 6 months ago

Log in to reply

I don't know whats exactly the issue but I cannot express at present

Anubhav Tyagi - 4 years, 6 months ago

truly marvellous...............ab bhai infinity hai to koi farak nahi padta +1 karo ya -1 :P , you rock bro ! ( i upvoted it !(+1))

A Former Brilliant Member - 4 years, 5 months ago
Chew-Seong Cheong
Dec 21, 2016

Relevant wiki: Linear Recurrence Relations - With Repeated Roots

f 1 ( x ) = x 2 + 10 f n ( x ) = f 1 ( f n 1 ( x ) ) f n ( x ) = f n 1 ( x ) 2 + 10 f n ( x ) 20 = 1 2 ( f n 1 ( x ) 20 ) Let g n = f n ( x ) 20 g n = 1 2 g n 1 Characteristic equation: 2 r 1 = 0 r = 1 2 g n = c 2 n g 1 = c 2 Note that g 1 = f 1 ( x ) 20 = x 2 10 c 2 = x 2 10 c = x 20 g n = x 20 2 n f n ( x ) 20 = x 20 2 n f n ( x ) = x 20 2 n + 20 lim n f n ( x ) = 20 \begin{aligned} f_1 (x) & = \frac x2 + 10 \\ f_n (x) & = f_1 \left(f_{n-1}(x)\right) \\ \implies f_n (x) & = \frac {f_{n-1}(x)}2 + 10 \\ f_n (x) - 20 & = \frac 12 \left(f_{n-1}(x) - 20 \right) & \small \color{#3D99F6} \text{Let }g_n = f_n(x) - 20 \\ \implies g_n & = \frac 12 g_{n-1} & \small \color{#3D99F6} \text{Characteristic equation: }2r-1=0 \implies r = \frac 12 \\ g_n & = \frac c{2^n} \\ g_1 & = \frac c2 & \small \color{#3D99F6} \text{Note that }g_1 = f_1(x) - 20 = \frac x2 - 10 \\ \frac c2 & = \frac x2 - 10 \\ \implies c & = x - 20 \\ \implies g_n & = \frac {x - 20}{2^n} \\ f_n (x) - 20 & = \frac {x-20}{2^n} \\ \implies f_n(x) & = \frac {x-20}{2^n} + 20 \\ \implies \lim_{n \to \infty} f_n(x) & = \boxed{20} \end{aligned}

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...