0

A recursive function is defined as follows-
$$f(1) = n-1 \\ f(i) = min\{f(i-1) + m), n\} - i$$
For what $i$, $f(i) \leq 0$?
Example: $n = 5, m = 2$ then -
$f(1) = n-1 = 4 \\ f(2) = min(4+2,5)-2 = 5-2 = 3 \\ f(3) = min(3 + 2,5) -3 = 2 \\ f(4) = min(2 +2,5) -4 = 0$
So answer is 4.

I don't know how to start. Any hint will be helpful.

Rezwan Arefin
  • 3,106
  • 1
  • 14
  • 39

1 Answers1

1

1) For $i \le m+1$, $f(i) = n-i$. Inductive proof is easy: $f(i-1)+m = n+(m-i+1) \ge n$. Thus for $n \le m+1$ the answer is $n$.
2) For $i = m+1+t$, let's suppose $f(i) = n-at^2-bt-c \le n-i$, then $$n-at^2-bt-c = n-at^2-bt-c+2at+b+m-m-1-t \\ a = b = {1 \over 2} \\ n-c = f(m+1) = n-m-1 \\ c = m+1$$ $f(m+t) = n - {t(t+1) \over 2} - m$ for $t \ge 0$ can be proven by induction as well. Thus for $n > m+1$ the answer is $m+t$ where $t^2+t-2(n-m) \le 0$ or $i = \lceil m + {\sqrt{1+8(n-m)}-1 \over 2} \rceil$. For $n=5, m=2$ this will give you $4$.

Abstraction
  • 2,482