An inductive proof is typically done with three steps:

  • Base Case
  • Inductive Hypothesis
  • Inductive Step

The argument that follows does not have a Base Case.

  • Is this approach valid (I believe that it is -- but I could be wrong)
  • Assuming this approach is valid, is my use of this approach valid (there could be a mistake in my reasoning)


$$H_n(x) = \sum\limits_{i |n\#}\left\lfloor\frac{x}{i}\right\rfloor\mu(i)$$


  • $H_n(x)$ is the count of $t$ where $t \le x$ and gcd$(t,n\#)=1$
  • $n\#$ is the primorial of $n$
  • $\mu(i)$ is the möbius function.

If $p_k$ is the $k$th prime, then:

$$H_{p_{k+1}}(x) = H_{p_k}(x) - H_{p_k}\left(\frac{x}{p_{k+1}}\right)$$

I was wondering if it is valid to use the following inductive argument with recurrent relations $W_k(n), d_k(n), c_k(n)$ where I do not define $W_0(n), c_0(n), d_0(n)$.


  • $W_k(x) = W_{k-1}(x) - \dfrac{W_{k-1}(x)}{p_k}$
  • $c_k = c_{k-1} + \dfrac{d_{k-1}}{p_k}$
  • $d_k = d_{k-1} + \dfrac{c_{k-1}}{p_k}$
  • $U_k(x) = W_k(x) + c_k$
  • $L_k(x) = W_k(x) - d_k$

Rather than defining $W_0(n), c_0, d_0$ which may or may not exist, assume that the following is valid up to $k$:

  • $U_k(x) \ge H_{p_k}(x) \ge L_k(x)$

  • $\dfrac{U_k(x)}{w} \ge H_{p_k}\left(\dfrac{x}{w}\right) \ge \dfrac{L_k(x)}{w}$ for all $1 \le w \le x$


  • $H_{p_{k+1}}(x) \le U_k(x) - \dfrac{L_k(x)}{p_{k+1}} \le W_k(x) - \dfrac{W_k(x)}{p_{k+1}} + c_k + \dfrac{d_k}{p_{k+1}} = W_{k+1}(x) + c_{k+1} = U_{k+1}(x)$
  • $H_{p_{k+1}}(x) \ge L_k(x) - \dfrac{U_k(x)}{p_{k+1}} \ge W_k(x) - \dfrac{W_k(x)}{p_{k+1}} - d_k - \dfrac{c_k}{p_{k+1}} = W_{k+1}(x) - d_{k+1} = L_{k+1}(x)$
  • $H_{p_{k+1}}\left(\dfrac{x}{w}\right) \le \dfrac{U_k(x) - \frac{L_k(x)}{p_{k+1}}}{w} \le \dfrac{W_k(x) - \frac{W_k(x)}{p_{k+1}} + c_k + \frac{d_k}{p_{k+1}}}{w} = \dfrac{W_{k+1}(x) + c_{k+1}}{w} = \dfrac{U_{k+1}(x)}{w}$
  • $H_{p_{k+1}}\left(\dfrac{x}{w}\right) \ge \dfrac{L_k(x) - \frac{U_k(x)}{p_{k+1}}}{w} \ge \dfrac{W_k(x) - \frac{W_k(x)}{p_{k+1}} - d_k - \frac{c_k}{p_{k+1}}}{w} = \dfrac{W_{k+1}(x) - d_{k+1}}{w} = \dfrac{L_{k+1}(x)}{w}$

Does this argument hold even if existence has not been proven?

Edit 1:

Adding details based on a flag that it is unclear what I am asking. Hopefully, this helps (details as a blockquote).

Please add a comment if the additional details do not help.

Edit 2:

Shortened the question based on a comment to my question here.


Yes, your argument does hold without proving a base case. Though you should make very clear that your argument is really just the inductive step;

If there exist $W_k(x)$, $c_k$, $d_k$, $U_k(x)$ and $L_k(x)$ satisfying the given recurrence relations, and

if the given inequalities hold for $k$, then they hold for $k+1$.

This does not prove that any of the inequalities hold; it does not even prove that such sequences exist. It does now suffice to prove a base case, for example by exhibiting such $W_0(x)$, $c_0$, $d_0$, $U_0(x)$ and $L_0(x)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.