Induction on digit sum

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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)$.