Test of Mathematics Solution Subjective 125 - Function on Natural Numbers

This is a Test of Mathematics Solution Subjective 125 (from ISI Entrance). The book, Test of Mathematics at 10+2 Level is Published by East West Press. This problem book is indispensable for the preparation of I.S.I. B.Stat and B.Math Entrance.

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.

Solution

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.

For second part we observe

$f(f(0)) = f(0)$
$f(f(1)) = f(1) (as f(1) = 1)$
As $f(2) = f(0) + f(1) = 1$, we have $f(f(2)) = f(1) = 1 = f(2)$.
Next observe that
- $f(3) = f(2) + f(1) = 1 + 1= 2$
- $f(4) = f(3) + f(2) = 2 + 1 = 3$
- $f(5) = f(4) + f(3) = 3 + 2 = 5$
- So $f(f(5)) = f(5)$ as $f(5) = 5$

So we got four numbers 0, 1, 2, 5, for which $f(f(n)) = f(n)$ by observation. We wish to show that this does not happen for any value of n greater than 5.

Clearly, if $f(f(n)) = f(n)$, then $f(n) = n$. We will show that $f(n) > n$ for all n greater than 5. (If we can show that then it will automatically show that f(n) is not equal n for any value greater than 5, implying f(f(n)) not equal to f(n) for any other value apart from the ones that we have found earlier by trial and error).

Note that $f(6) = f(5) + f(4) = 5 + 3 = 8$. That is $f(6) > 6$. Similarly $f(7) = f(6)+ f(5) = 8+5 = 13$ implying $f(7)> 7$.

We will again use strong for of induction. Suppose $f(k) > k$ for all values of k from 6 to n $ n \ge 7 $. Using this assumption we will show that $f(n+1) > n+1$.

$f(n+1) = f(n) + f(n-1)$. By induction $f(n) > n$ and $f(n-1) > n-1$. This implies $f(n+1) > n + n -1 = 2n -1$.

But $2n-1 > n+1$ (as n > 2). Hence it follows that $f(n+1) > n+1$. This solves second part.

Finally we wish to show that 5 divides f(5n).

We again use induction. First note that f(5) = 5 hence divisible by 5. Assume that the claim is true for n-1. That is 5 divides f(5(n-1)). Using this assumption we wish to show that 5 divides f(5n). Now note that:

$f(5n)$

= $f(5n-1) + f(5n-2)$

= $f(5n-2) + f(5n-3) + f(5n-3) + f(5n-4)$

= $f(5n-3) + f(5n-4) + f(5n- 4) + f(5n-5) + f(5n-4) + f(5n- 5) + f(5n - 4)$

= $f(5n-4) + f(5n-5) + f(5n-4) + f(5n- 4) + f(5n-5) + f(5n-4) + f(5n- 5) + f(5n - 4)$

= $5 f(5n-4) + 3 f(5n-5)$

Clearly 5 $f(5n-4)$ is divisible by 5. Also $3 f(5n-5)$ is divisible by 5 as by inductive assumption $f(5n-5)$ is divisible by 5. Hence their sum 5 $f(5n-4) + 3 f(5n-5)$ is divisible by 5. This shows 5 divides 5 divides $f(5n)$.

This completes the proof of third part.

Comments:

Actually the problem is more fun if we bring in ideas of fibonacci numbers and work with it's analytical form by solving the linear recurrence given here.

Chatuspathi:

What is this topic: Mathematical Induction
What are some of the associated concept: Fibonacci Numbers, Linear Recurrences
Where can learn these topics: I.S.I. & C.M.I. Entrance course of Cheenta, discusses these topics in the ‘Number Theory’ module.
Book Suggestions: Elementary Number Theory by David Burton

ISI MStat PSB 2005 Problem 1 | The Inductive Matrix

This is a very beautiful sample problem from ISI MStat PSB 2005 Problem 1. It is based on some basic properties of upper triangular matrix and diagonal matrix, only if you use them carefully. Give it a thought!

Problem- ISI MStat PSB 2005 Problem 1

Let $A$ be a $n \times n$ upper triangular matrix such that $AA^T=A^TA$. Show that $A$ is a diagonal matrix.

Prerequisites

Upper Triangular Matrix

Diagonal Matrix

Mathematical Induction

Solution :

This is very beautiful problem, since it deals with some very beautiful aspects of matrix. Lets assume the matrix $A$ to be,

$A=\begin{bmatrix} a_{11} & \vec{{a_1}^T} \\ \vec{0_{n-1}}& A_{n-1} \end{bmatrix} $.

Here, $A_{n-1}$ is a partition matrix of $A$, which is also an upper triangular matrix of order $n-1$, and $\vec{0_{n-1}}$ is a null column vector of order $n-1$.

So, $ AA^T= \begin{bmatrix} {a_{11}}^2+\vec{{a_1}^T}\vec{a_1} && \vec{{a_1}^T}{A_{n-1}}^T \\ A_{n-1}\vec{a_1}&& A_{n-1}{A_{n-1}}^T \end{bmatrix} $ .

Again, $ A^TA= \begin{bmatrix} {a_{11}}^2&& a_{11}\vec{a_1} \\ a_{11}\vec{a_1}&& \vec{a_1}\vec{{a_1}^T}+{A_{n-1}}^TA_{n-1} \end{bmatrix} $.

Now lets assume that when a $n\times n$ upper triangular matrix $A$, holds $AA^T=A^TA$ , then $A$ is diagonal is true. Then equating the above elements, we have,

$\vec{{a_1}^T}\vec{a_1}=0 \Rightarrow \vec{a_1}=\vec{0}$ , and also $A_{n-1}{A_{n-1}}^T={A_{n-1}}^TA_{n-1}$.

Now observe that, if $A_{n-1}$ (which is actually an $n\times n$ upper triangular matrix), is a diagonal matrix then only $A$ will be also diagonal. So, its the same problem we are trying to prove !! So, just use induction get the proof done !!

Food For Thought

What if I change the given relation as $AA^*=A^*A$, where $A^*$ is the conjugate matrix of $A$, rest of the conditions remains same. Can you investigate whether $A$ is a diagonal matrix or not ?

Keep thinking !!

Outstanding Statistics Program with Applications

Inequality of fractions - TOMATO Subjective 12

Inequality of fractions

An inequality is a relation which makes a non-equal comparison between two numbers or other mathematical expressions. It is used most often to compare two numbers on the number line by their size. In this post we are going to discuss a problem on inequality of fractions.

Try the problem

This problem is from Indian Statistical Institute

Let $$ x_n = \frac {1}{2} \cdot \frac{3}{4} \cdot \frac {5}{6} \cdots \frac{2n-1}{2n} $$

Then show that $$ x_n \leq \frac {1} {\sqrt{3n+1} } $$

Test of Mathematics at 10 + 2 Level, problem 12, Subjective. This is also an old Math Olympiad Problem and entrance of Indian Statistical Institute (B.Stat, B.Math)

Inequalities (Algebra), Mathematical Induction

6 out of 10

Secrets in Inequalities by Pham Kim Hung

Use some hints

This can be easily proved by mathematical induction.

First, check that the claim is true for n=1

That is $$ x_1 = \frac{1}{2} \geq \frac{1}{\sqrt{3\times 1 + 1}} = \frac{1}{2}$$

Now assume that, it is true for n = k. That is, assume $$ x_k = \frac {1}{2} \cdots \frac{2k-1}{2k} \leq \frac {1} {\sqrt{3k+1} } $$

Finally, prove that it is true for n = k +1

Let us write the expression for n = k+1.

$$ x_{k+1} = \frac {1}{2} \cdots \frac{2k-1}{2k} \cdot \frac{2(k+1)-1}{2(k+1)} $$

Since $$ x_k = \frac {1}{2} \cdots \frac{2k-1}{2k} \leq \frac {1} {\sqrt{3k+1} } $$

We can replace the first portion of ( x_{k+1} ) by ( \frac {1} {\sqrt{3k+1} } ) and the resultant quantity will be greater than ( x_{k+1} )

Particularly

$$ x_{k+1} \leq \frac {1} {\sqrt{3k+1}} \cdot \frac{2(k+1)-1}{2(k+1)} =\frac {1} {\sqrt{3k+1}} \cdot \frac{2k+1}{2k+2}$$

We want to show that $$ x_{k+1} \leq \frac{1} {\sqrt{3\times (k+1) + 1} } $$

We found something even larger than ( x_{k+1} ), that is ( \frac {1} {\sqrt{3k+1} } \cdot \frac{2k+1}{2k+2} )

If we can show that this larger quantity is smaller than ( \frac{1} {\sqrt{3\times (k+1) + 1} } ) then certainly ( x_{k+1} ) will be smaller than ( \frac{1} {\sqrt{3\times (k+1) + 1 }} ).

Suppose otherwise (proof by contradiction).

Assume that ( \frac {1} { \sqrt {3k+1} } \cdot \frac{2k+1}{2k+2} > \frac{1} { \sqrt{ 3\times (k+1) + 1 } } )

Simplifying this inequality leads to contradiction.

For example, square both sides and cross multiply to find

$$ ( \sqrt{3k+4})^2 \times (2k+1)^2 > (\sqrt{3k+1})^2 \times (2k+2)^2 $$

Expand and simplify both sides to find $$ 12 k^3 + 28 k^2 + 19k + 4 > 12 k^3 + 28 k^2 + 20k + 4 $$

Cancelling everything we are left out with $$ 19k > 20k $$

Hence contradiction.

I.S.I., C.M.I. Entrance Program at Cheenta

Taught by Olympians, I.S.I. students, alumni, and researchers from leading universities in the world.

Group + One-on-One Classes + 24/7 Doubt Clearing Forum

Test of Mathematics Solution Subjective 125 - Function on Natural Numbers

Problem

Solution

Chatuspathi:

ISI MStat PSB 2005 Problem 1 | The Inductive Matrix

Problem- ISI MStat PSB 2005 Problem 1

Prerequisites

Solution :

Food For Thought

Similar Problems and Solutions

Outstanding Statistics Program with Applications

Inequality of fractions - TOMATO Subjective 12

Inequality of fractions

Try the problem

Use some hints

Other useful links

I.S.I., C.M.I. Entrance Program at Cheenta

Problem

Solution

Chatuspathi:

Problem- ISI MStat PSB 2005 Problem 1

Prerequisites

Solution :

Food For Thought

Similar Problems and Solutions

Related Program

Outstanding Statistics Program with Applications

Subscribe to Cheenta at Youtube

Inequality of fractions

Try the problem

Use some hints

Other useful links

Related Program

I.S.I., C.M.I. Entrance Program at Cheenta

Subscribe to Cheenta at YouTube