• No products in the cart.

Profile Photo

Function on natural numbers (Tomato subjective 125)

Problem: Let \(f: \mathcal{N} to \mathcal{N} \) be the function defined by f(0) = 0, f(1) = 1, and f(n) = f(n-1) + f(n-2), for \(n \ge 2 \), where \(\mathcal {N} \) is the set of all non negative integers. Prove the following results:

  • f(n) < f(n+1) for all \( n \ge 2 \)
  • There exists precisely four non-negative integers n for which f(f(n)) = f(n).
  • f(5n) is divisible by 5, for all n.

Discussion: This problem gives us an opportunity to discuss Fibonacci Sequence (which is defined by this function) and solving linear recursions. However none of these two discussions are necessary to solve the problem. Hence we leave those discussions for class and focus on the solution itself:

Clearly f(2) = 1, and f(3) = f(2) + f(1) = 2. Hence  f(3) is positive. We use strong form of induction and assume that up to n, all f(n) is positive.

Then f(n+1) = f(n) + f(n-1) .

Since f(n-1) is positive. Hence f(n+1) > f(n). This solves first part.

Read More…

November 20, 2015

No comments, be the first one to comment !

    Leave a Reply

    Your email address will not be published. Required fields are marked *



    GOOGLECreate an Account