# Induction on digit sum

In this thread: https://artofproblemsolving.com/community/c6h2692613p23375837 there is a hint, that in order to prove $$\prod_{i=1}^{n}S(2i-1) \geq \prod_{i=1}^{n}S(2i)$$ for all $$n \geq 5$$, one can use induction. Here, $$S(n)$$ is the digit sum.

I can show here that using induction (I omit the base step here) to get $$\prod_{i=1}^{n+1}S(2i-1)=\prod_{i=1}^{n}S(2i-1)S(2(n+1)-1) \geq \prod_{i=1}^{n}S(2i)S(2n+1)$$ but I cannot get $$\prod_{i=1}^{n}S(2i)$$ Any hints would be great... thanks in advance.

Standard induction with a step size of $$1$$ will not be enough since $$S(2n+2)$$ is not always $$\ge S(2n+1)$$ (think what happens when the last digit of $$2n+1$$ is $$9$$). You'll likely need to consider induction with a step size of $$5$$ and a bit of case work, ie, consider $$P(n)$$ to be the proposition $$\prod_1^n S(2i-1)\ge\prod_1^n S(2i)$$. Prove the base cases $$P(5),P(6),\ldots, P(9)$$ and show the inductive step $$P(n)\rightarrow P(n+5)$$.

Another concern will be to keep track of how many trailing $$9$$s does $$2n-1$$ has, as this will have a big effect on what $$S(2n+1)$$ is. The simplest case is when $$2n-1$$ has just one trailing $$9$$, because then $$S(2n+1)=S(2n-1)-9+2$$ and the numbers $$2n+1,2n+3,2n+5,2n+7,2n+9$$ all have the same digits except for their last digits, which will be $$1,3,5,7,9$$ respectively.

If $$2n-1$$ does not end with $$9$$ (ie, ends with $$1/3/5/7$$), then $$S(2n)=S(2n-1)+1$$ and $$S(2n+1)=S(2n-1)+2$$, and standard induction takes with step size of $$1$$ takes care of it.

A complete proof should be easy to produce with the above ideas, albeit tedious.

Let $$O(n)=\prod_{i=1}^nS(2i-1)$$ and $$E(n)=\prod_{i=1}^nS(2i)$$, we want to show $$O(n)\geq E(n)$$.

Main idea: Instead of assuming $$O(n)\geq E(n)$$ it easier to assume $$O(n)/E(n)\geq$$ something, and, instead of step-$$1$$ induction it is better to use step-$$5$$ induction (since $$O(n)/E(n)$$ increases every $$5$$ steps). Here is a proof sketch:

The main assumption is $$\frac{O(5m)}{E(5m)}\geq\frac{315}{128}\quad\forall m\in\mathbb Z^+. \tag{\star}$$

Base case: We simply have $$\frac{O(5)}{E(5)}=\frac{315}{128}$$.

Induction: Assume $$(\star)$$ holds for $$m\geq1$$. For $$n>5$$, write $$n=5m+d$$ with reminder $$d\in\{1,2,3,4,5\}$$. We denote by $$o(n)=\prod_{i=5m+1}^nS(2i-1)$$ and $$e(n)=\prod_{i=5m+1}^nS(2i)$$. For $$d<5$$, we have

$$\frac{e(n)}{o(n)}=\frac{(m+2)(m+4)\cdots(m+2d)}{(m+1)(m+3)\cdots(m+2d-1)}.$$

The above fraction is increasing in $$d$$ and decreasing in $$m$$, thus $$\frac{e(n)}{o(n)}\leq\frac{3\cdot5\cdot7\cdot9}{2\cdot4\cdot6\cdot8}=\frac{315}{128}$$. This implies

$$O(n)-E(n)=o(n)\left(O(5m)-\frac{e(n)}{o(n)}E(5m)\right)\geq o(n)\left(O(5m)-\frac{315}{128}E(5m)\right)\geq0$$

by $$(\star)$$. As for $$d=5$$, we have

$$\frac{e(n)}{o(n)}=\frac{(m+2)(m+4)(m+6)(m+8)(m+1)}{(m+1)(m+3)(m+5)(m+7)(m+9)}\leq1.$$

Hence $$O(n)-E(n)\geq o(n)(O(5m)-E(5m))$$ and it follows

$$\frac{O(n)}{E(n)}\geq o(n)\left(\frac{O(5m)}{E(5m)}-1\right)+1\geq o(n)\left(\frac{315}{128}-1\right).$$ Since $$o(n)\geq2$$, we have $$\frac{O(n)}{E(n)}\geq\frac{315}{128}$$ with $$n=5(m+1)$$. This concludes the induction step.

Let $$A(n)= \prod_{i=1}^{n}S(2i-1), \qquad B(n)= \prod_{i=1}^{n}S(2i)$$

Suppose we have shown $$A(n)\geq B(n)$$ for all values of $$n\geq 5$$ up to $$5k-1$$. We will show that $$A(n)\geq B(n)$$ holds for all values of $$n$$ up to $$5(k+1)-1$$. Thus after checking values of $$n$$ up to 9, we are done by induction on $$k$$.

Clearly $$2(5k)=10k$$ has $$0$$ as its last digit. Thus $$2(5k+i)$$ for $$i=0,1,2,3,4$$ will all have identical digits except for the last one, and $$B(5k+4)/B(5k-1)$$ is the product of $$x,x+2,x+3,x+4,x+6, x+8,\qquad (1)$$ where $$x=S(10k)$$. Let $$y=S(10k-1)$$. Then $$A(5k+4)/A(5k-1)$$ is the product of $$y,x+1,x+3,x+5,x+7. \qquad (2)$$

Note that the last four terms listed in $$(1)$$ are larger than their counterparts in $$(2)$$. Thus if the inequality failed for any value of $$n$$ in the range $$5k,5k+1,5k+2,5k+3,5k+4$$, then it would fail for $$n=5k+4$$.

Next note that $$y\geq x+8$$, as adding $$1$$ to $$10k-1$$ will result in at least one digit $$9$$ being replaced by a digit $$0$$, and the only other change to the digits is one of them being increased by $$1$$.

Thus we have $$y\geq x+8, \qquad x+1>x,\qquad x+3>x+2,$$ $$x+5>x+4,\qquad x+7>x+6,$$ so the product of the terms in $$(2)$$ is greater than the product of the terms in $$(1)$$.