jmc

Let $n=10^9+1.$ Then we want the smallest $k$ so that $$\left(\genfrac{}{}{0ex}{}{n-1}{k}\right)<\left(\genfrac{}{}{0ex}{}{n}{k-1}\right).$$Using the formula for a binomial coefficient, we get $$\frac{(n-1)!}{k!(n-k-1)!}<\frac{n!}{(k-1)!(n-k+1)!}.$$Then $$(n-k+1)(n-k)<nk.$$We consider the easier inequality $(n-k{)}^2<nk.$ Then $n^2-2nk+k^2<nk,$ or $k^2-3nk+n^2<0.$ By the quadratic formula, the roots of the corresponding equation $k^2-3nk+n^2=0$ are $$\frac{3\pm \sqrt{5}}{2}\cdot n.$$So if $(n-k{)}^2<nk,$ we must have $k>\alpha n,$ where $\alpha =\frac{3-\sqrt{5}}{2}.$ Note that ${\alpha }^2-3\alpha +1=0.$

If $k<\alpha n$, then $$\begin{array}{rl}(n-k+1)(n-k)& >(n-k{)}^2\\ & >(n-\alpha n{)}^2\\ & =(1-\alpha {)}^2{n}^2\\ & =(1-2\alpha +{\alpha }^2)n^2\\ & =\alpha n^2\\ & =n(\alpha n)>nk.\end{array}$$On the other hand, if $k>\alpha (n+1),$ then $$\begin{array}{rl}(n-k+1)(n-k)& =(n+1-\alpha (n+1))(n-\alpha (n+1))\\ & <(n+1)(1-\alpha )n(1-\alpha )\\ & =(1-2\alpha +{\alpha }^2)n(n+1)\\ & =\alpha n(n+1)\\ & <nk.\end{array}$$Therefore, the smallest such $k$ satisfies $$\alpha n<k<\alpha (n+1).$$For $n=10^9+1,$ this gives us $$3819660\dots <n<3819660\dots ,$$so $a=3$ and $b=8,$ and the final answer is $\boxed{38}.$