Question 14

A function $$𝑓$$ is defined on the set of integers such that for any two integers $$π‘š$$ and $$n$$, $$f(mn + 1) = f(m)f(n) - f(n) - m + 2$$ holds and $$f(0)=1$$. Determine the largest positive integer $$𝑁$$ such that $$\sum_{k=1}^{N}f(k) < 100$$.


Correct Answer: 12

The functional equation is

$$f(mn+1)=f(m)\,f(n)-f(n)-m+2$$ for all integers $$m,n$$, with the initial value $$f(0)=1$$.

Step 1: Evaluate $$f(1)$$
Put $$m=0$$ in the equation:

$$f(0\cdot n+1)=f(0)\,f(n)-f(n)-0+2$$
$$\Longrightarrow\;f(1)=1\cdot f(n)-f(n)+2=2$$ (independent of $$n$$).

Step 2: Guess a simple candidate
The values $$f(0)=1$$ and $$f(1)=2$$ suggest the linear rule $$f(k)=k+1$$. Check it directly:

LHS: $$f(mn+1)=mn+1+1=mn+2$$
RHS: $$f(m)f(n)-f(n)-m+2=(m+1)(n+1)-(n+1)-m+2$$
$$=(mn+m+n+1)-n-1-m+2=mn+2$$

Both sides are equal, so $$f(k)=k+1$$ satisfies the functional equation.

Step 3: Show $$f(k)=k+1$$ for all non-negative integers
We prove by induction.

Base cases: $$f(0)=1=0+1$$ and $$f(1)=2=1+1$$.

Inductive step: Assume $$f(m)=m+1$$ for some $$m\ge 0$$. Take $$n=1$$ in the functional equation:

$$f(m\cdot1+1)=f(m)f(1)-f(1)-m+2$$
$$\Rightarrow f(m+1)=f(m)\cdot2-2-m+2=2f(m)-m$$

Substitute the induction hypothesis $$f(m)=m+1$$:

$$f(m+1)=2(m+1)-m=m+2=(m+1)+1$$

Thus the statement holds for $$m+1$$. By induction, $$f(k)=k+1$$ for every non-negative integer $$k$$.

Step 4: Sum of the first $$N$$ values
$$\sum_{k=1}^{N}f(k)=\sum_{k=1}^{N}(k+1)=\sum_{k=1}^{N}k+\sum_{k=1}^{N}1$$
$$=\frac{N(N+1)}{2}+N=\frac{N(N+3)}{2}$$

Step 5: Impose the condition
We need

$$\frac{N(N+3)}{2}\lt100$$ $$\Longrightarrow N(N+3)\lt200$$ $$\Longrightarrow N^{2}+3N-200\lt0$$

The positive root of $$N^{2}+3N-200=0$$ is

$$N=\frac{-3+\sqrt{9+800}}{2}=\frac{-3+\sqrt{809}}{2}\approx12.72$$

Therefore $$N$$ must be the greatest integer strictly less than $$12.72$$, i.e. $$N=12$$.

Hence the largest positive integer satisfying the given inequality is 12.

Get AI Help

Video Solution

video

Book Free CAT Mentorship

Get personalized CAT strategy from a 99%iler

500+ students mentored
CAT mentor
banner

banner

50,000+ JEE Students Trusted Our Score Calculator

Predict your JEE Main percentile, rank & performance in seconds

Ask AI