**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…

*Related*

## No comments, be the first one to comment !