We all know that $\sum\_{k=0}^n\binom{n}k$ is not divisible by $3$.



> 
> **QUESTION.** Is it true that the numerator of $a\_n$ (in reduced form) is never divisible by $3$?
>  $$a\_n=\sum\_{k=0}^n\frac1{\binom{n}k}.$$
> 
> 
> 


**POSTSCRIPT.** This the most detailed and pedagogical answer to any question that I asked here on MO. Thank you, Darij Grinberg. 



Reciprocal sum of binomials and divisibility by $3$
Here is the answer I hinted at in a comment, in real detail. Took me a while,
but I had no idea how tiresome such arguments are to expose...


Yes, it is true: see Corollary 6 **(b)** below. The proof relies on the
concept of a $p$-adic valuation of a rational number. It is defined as follows:



> 
> **Definition.** Let $p$ be a prime. For each rational number $r$, we shall now
>  define an element $v\_{p}\left( r\right) $ of the set $\mathbb{Z}\cup\left\{
> \infty\right\} $ (where $\infty$ is understood to be a symbol that satisfies
>  the rules $\infty\geq n$ and $\infty+n=\infty$ for all $n\in\mathbb{Z}
> \cup\left\{ \infty\right\} $). We define it in three steps:
> 
> 
> * If $r=0$, then we set $v\_{p}\left( r\right) =\infty$.
> * If $r\in\mathbb{Z}$, then we let $v\_{p}\left( r\right) $ be the largest
>  $k\in\mathbb{N}$ satisfying $p^{k}\mid r$. (Here and in the following,
>  $\mathbb{N}$ means the set $\left\{ 0,1,2,\ldots\right\} $.)
> * If $r$ is any nonzero rational number, then we define $v\_{p}\left(
> r\right) $ by $v\_{p}\left( r\right) =v\_{p}\left( a\right) -v\_{p}\left(
> b\right) $, where $a$ and $b$ are two nonzero integers satisfying $r=a/b$.
>  (This is well-defined, since any nonzero rational number $r$ can be written as
>  $r=a/b$ for two nonzero integers $a$ and $b$, and since $v\_{p}\left(
> a\right) -v\_{p}\left( b\right) $ does not depend on the specific choice of
>  $a$ and $b$. Also, this new definition of $v\_{p}\left( r\right) $ for
>  rational numbers $r$ does not conflict with the previous definition of
>  $v\_{p}\left( r\right) $ for integers $r$. This is all easy to check.)
> 
> 
> Thus, an element $v\_{p}\left( r\right) \in\mathbb{Z}\cup\left\{
> \infty\right\} $ has been defined for each $r\in\mathbb{Q}$. This element
>  $v\_{p}\left( r\right) $ will be called the *$p$-adic valuation of $r$*.
> 
> 
> 


We will need the following rules for $p$-adic valuations:



> 
> **Proposition 1.** Let $p$ be a prime.
> 
> 
> **(a)** We have $v\_{p}\left( ab\right) =v\_{p}\left( a\right) +v\_{p}\left(
> b\right) $ for any $a,b\in\mathbb{Q}$.
> 
> 
> **(b)** We have $v\_{p}\left( a+b\right) \geq\min\left\{ v\_{p}\left(
> a\right) ,v\_{p}\left( b\right) \right\} $ for any $a,b\in\mathbb{Q}$.
> 
> 
> **(c)** We have $v\_{p}\left( a^{k}\right) =kv\_{p}\left( a\right) $ for any
>  $a\in\mathbb{Q}$ and $k\in\mathbb{N}$.
> 
> 
> **(d)** For any $i\in\mathbb{N}$ and $n\in\mathbb{Z}$, we have the equivalence
>  $\left( p^{i}\mid n\right) \ \Longleftrightarrow\ \left( v\_{p}\left(
> n\right) \geq i\right) $.
> 
> 
> **(e)** If $a,b\in\mathbb{Q}$ satisfy $v\_{p}\left( a\right) >v\_{p}\left(
> b\right) $, then $v\_{p}\left( a+b\right) =v\_{p}\left( b\right) $.
> 
> 
> **(f)** Let $s$ and $t$ be two coprime integers such that $t\neq0$ and
>  $v\_{p}\left( \dfrac{s}{t}\right) \leq0$. Then, $p\nmid s$.
> 
> 
> 


*Proof of Proposition 1.* This is all well-known. Just in case, here are a few pointers:


Parts **(a)** and **(b)** of Proposition 1 are obvious in the case when one of
$a$ and $b$ is $0$ (because $v\_{p}\left( 0\right) =\infty\geq g$ for all
$g\in\mathbb{Z}\cup\left\{ \infty\right\} $). Thus, they only need to be
proven in the case when both $a$ and $b$ are nonzero. But in this case, they
are exactly the parts **(c)** and **(d)** of Exercise 3.4.1 in [my *Introduction to Modern Algebra*
notes (version of 31 May 2019)](http://www.cip.ifi.lmu.de/~grinberg/t/19s/notes.pdf) (the numbering might change in the future, but you can always find the version of 31 May 2019 frozen [on github](https://github.com/darijgr/algebra19s/releases/tag/2019-05-31)). (Be
warned that, in the latter notes, I use two different notations for what I am
here calling $v\_{p}\left( r\right) $: The first notation is "$v\_{p}\left(
r\right) $", which I use only in the case when $r$ is an integer; the second
notation is "$w\_{p}\left( r\right) $", which I use in the general case of
rational $r$. The reason why I do this is to avoid a conflict of notations,
even a theoretical one that doesn't actually happen; the notes are written for undergraduates.)


Proposition 1 **(c)** follows by induction on $k$. (The induction base uses
$v\_{p}\left( 1\right) =0$, while the induction step uses Proposition 1 **(a)**.)


Proposition 1 **(d)** is Lemma 2.13.25 in [my *Introduction to Modern Algebra*
notes (version of 31 May 2019)](http://www.cip.ifi.lmu.de/~grinberg/t/19s/notes.pdf) (the numbering might change in the future, but you can always find the version of 31 May 2019 frozen [on github](https://github.com/darijgr/algebra19s/releases/tag/2019-05-31)). It is essentially a direct consequence of the
definition of $v\_{p}\left( n\right) $.


**(e)** Let $a,b\in\mathbb{Q}$ satisfy $v\_{p}\left( a\right) >v\_{p}\left(
b\right) $. We must prove that $v\_{p}\left( a+b\right) =v\_{p}\left(
b\right) $.


Assume the contrary. Thus, $v\_{p}\left( a+b\right) \neq v\_{p}\left(
b\right) $. But Proposition 1 **(b)** yields $v\_{p}\left( a+b\right)
\geq\min\left\{ v\_{p}\left( a\right) ,v\_{p}\left( b\right) \right\}
=v\_{p}\left( b\right) $ (since $v\_{p}\left( a\right) >v\_{p}\left(
b\right) $). Combined with $v\_{p}\left( a+b\right) \neq v\_{p}\left(
b\right) $, this yields $v\_{p}\left( a+b\right) >v\_{p}\left( b\right) $.
On the other hand, $v\_{p}\left( \underbrace{-a}\_{=a\left( -1\right)
}\right) =v\_{p}\left( a\left( -1\right) \right) =v\_{p}\left( a\right)
+v\_{p}\left( -1\right) $ (by Proposition 1 **(a)**, applied to $b=-1$).
Since $-1$ is an integer, we have $v\_{p}\left( -1\right) \geq0$. (Actually,
$v\_{p}\left( -1\right) =0$, but we don't need this.) Now, $v\_{p}\left(
-a\right) =v\_{p}\left( a\right) +\underbrace{v\_{p}\left( -1\right)
}\_{\geq0}\geq v\_{p}\left( a\right) >v\_{p}\left( b\right) $. Hence, both
$v\_{p}\left( a+b\right) $ and $v\_{p}\left( -a\right) $ are $>v\_{p}\left(
b\right) $ (since we know that $v\_{p}\left( a+b\right) >v\_{p}\left(
b\right) $). Thus, $\min\left\{ v\_{p}\left( a+b\right) ,v\_{p}\left(
-a\right) \right\} >v\_{p}\left( b\right) $ (since $\min\left\{
v\_{p}\left( a+b\right) ,v\_{p}\left( -a\right) \right\} $ must be one of
the numbers $v\_{p}\left( a+b\right) $ and $v\_{p}\left( -a\right) $).


But $b=\left( a+b\right) +\left( -a\right) $. Hence,
\begin{align\*}
v\_{p}\left( b\right) =v\_{p}\left( \left( a+b\right) +\left( -a\right)
\right) \geq\min\left\{ v\_{p}\left( a+b\right) ,v\_{p}\left( -a\right)
\right\}
\end{align\*}
(by Proposition 1 **(b)**, applied to $a+b$ and $-a$ instead of $a$ and $b$).
This contradicts $\min\left\{ v\_{p}\left( a+b\right) ,v\_{p}\left(
-a\right) \right\} >v\_{p}\left( b\right) $. This contradiction shows that
our assumption was wrong. Hence, Proposition 1 **(e)** is proven.


**(f)** Assume the contrary. Thus, $p\mid s$. Hence, $p^{1}=p\mid s$. But
Proposition 1 **(d)** (applied to $i=1$ and $n=s$) shows that we have the
equivalence $\left( p^{1}\mid s\right) \ \Longleftrightarrow\ \left(
v\_{p}\left( s\right) \geq1\right) $. Hence, we have $v\_{p}\left( s\right)
\geq1$ (since $p^{1}\mid s$).


But Proposition 1 **(a)** (applied to $a=\dfrac{s}{t}$ and $b=t$) yields
$v\_{p}\left( \dfrac{s}{t}\cdot t\right) =\underbrace{v\_{p}\left( \dfrac
{s}{t}\right) }\_{\leq0}+v\_{p}\left( t\right) \leq v\_{p}\left( t\right) $.
Hence, $v\_{p}\left( t\right) \geq v\_{p}\left( \underbrace{\dfrac{s}{t}\cdot
t}\_{=s}\right) =v\_{p}\left( s\right) \geq1$. But Proposition 1 **(d)**
(applied to $i=1$ and $n=t$) shows that we have the equivalence $\left(
p^{1}\mid t\right) \ \Longleftrightarrow\ \left( v\_{p}\left( t\right)
\geq1\right) $. Hence, we have $p^{1}\mid t$ (since $v\_{p}\left( t\right)
\geq1$). Thus, $p=p^{1}\mid t$.


Now, $p$ is a common divisor of $s$ and $t$ (since $p\mid s$ and $p\mid t$).
This shows that $s$ and $t$ have a common divisor larger than $1$ (since
$p>1$); but this contradicts the fact that $s$ and $t$ are coprime. This
contradiction shows that our assumption was false. Thus, Proposition 1 **(f)**
is proven. $\blacksquare$


Next, we need a binomial identity:



> 
> **Proposition 2.** Let $n\in\mathbb{N}$. Then,
>  \begin{align\*}
> \sum\limits\_{k=0}^{n}\dfrac{1}{\dbinom{n}{k}}=\dfrac{n+1}{2^{n+1}}\sum\limits\_{k=1}
> ^{n+1}\dfrac{2^{k}}{k}.
> \end{align\*}
> 
> 
> 


Proposition 2 is the equality (7) in <https://math.stackexchange.com/a/481686/>
; it is also Exercise 3.20 **(b)** in [my *Notes on the combinatorial
fundamentals of algebra*, version of
2019-01-10](https://github.com/darijgr/detnotes/releases/tag/2019-01-10).
$\blacksquare$


Next, we need two specific $3$-adic valuations:



> 
> **Lemma 3.** Let $k$ be a positive integer.
> 
> 
> **(a)** We have $v\_{3}\left( \dfrac{2^{k}}{k}\right) =-v\_{3}\left(
> k\right) $.
> 
> 
> **(b)** If $k$ is odd, then $v\_{3}\left( \dfrac{2^{k}}{k}+\dfrac{2^{2k}}
> {2k}\right) =-v\_{3}\left( k\right) $.
> 
> 
> 


*Proof of Lemma 3.* Clearly, $2^{k}$ is an integer; thus, $v\_{3}\left(
2^{k}\right) \in\mathbb{N}$. Similarly, $v\_{3}\left( 1+2^{k-1}\right)
\in\mathbb{N}$.


We don't have $3^{1}\mid2^{k}$ (since the only prime divisor of $2^{k}$ is
$2$). Proposition 1 **(d)** (applied to $p=3$, $i=1$ and $n=2^{k}$) yields the
equivalence $\left( 3^{1}\mid2^{k}\right) \ \Longleftrightarrow\ \left(
v\_{3}\left( 2^{k}\right) \geq1\right) $. Hence, we don't have $v\_{3}\left(
2^{k}\right) \geq1$ (since we don't have $3^{1}\mid2^{k}$). In other words,
we have $v\_{3}\left( 2^{k}\right) <1$; thus, $v\_{3}\left( 2^{k}\right) =0$
(since $v\_{3}\left( 2^{k}\right) \in\mathbb{N}$).


**(a)** Proposition 1 **(a)** (applied to $p=3$, $a=\dfrac{2^{k}}{k}$ and
$b=k$) yields $v\_{3}\left( \dfrac{2^{k}}{k}\cdot k\right) =v\_{3}\left(
\dfrac{2^{k}}{k}\right) +v\_{3}\left( k\right) $. Comparing this with
$v\_{3}\left( \underbrace{\dfrac{2^{k}}{k}\cdot k}\_{=2^{k}}\right)
=v\_{3}\left( 2^{k}\right) =0$, we obtain $v\_{3}\left( \dfrac{2^{k}}
{k}\right) +v\_{3}\left( k\right) =0$. Hence, $v\_{3}\left( \dfrac{2^{k}}
{k}\right) =-v\_{3}\left( k\right) $. This proves Lemma 3 **(a)**.


**(b)** Assume that $k$ is odd. Thus, $k-1$ is even. Now, $2\equiv
-1\operatorname{mod}3$ and thus $2^{k-1}\equiv\left( -1\right)
^{k-1}=1\operatorname{mod}3$ (since $k-1$ is even). Hence,
$1+\underbrace{2^{k-1}}\_{\equiv1\operatorname{mod}3}\equiv1+1=2\not \equiv
0\operatorname{mod}3$, so that $3\nmid1+2^{k-1}$. But Proposition 1 **(d)**
(applied to $p=3$, $i=1$ and $n=1+2^{k-1}$) yields the equivalence $\left(
3^{1}\mid1+2^{k-1}\right) \ \Longleftrightarrow\ \left( v\_{3}\left(
1+2^{k-1}\right) \geq1\right) $. Hence, we don't have $v\_{3}\left(
1+2^{k-1}\right) \geq1$ (since we don't have $3^{1}\mid1+2^{k-1}$ (because
$3^{1}=3\nmid1+2^{k-1}$)). In other words, we have $v\_{3}\left(
1+2^{k-1}\right) <1$; thus, $v\_{3}\left( 1+2^{k-1}\right) =0$ (since
$v\_{3}\left( 1+2^{k-1}\right) \in\mathbb{N}$).


Now, Proposition 1 **(a)** (applied to $p=3$, $a=\dfrac{2^{k}}{k}$ and
$b=1+2^{k-1}$) yields
\begin{align\*}
v\_{3}\left( \dfrac{2^{k}}{k}\left( 1+2^{k-1}\right) \right) =v\_{3}\left(
\dfrac{2^{k}}{k}\right) +\underbrace{v\_{3}\left( 1+2^{k-1}\right) }
\_{=0}=v\_{3}\left( \dfrac{2^{k}}{k}\right) =-v\_{3}\left( k\right)
\end{align\*}
(by Lemma 3 **(a)**). In view of
\begin{align\*}
\dfrac{2^{k}}{k}\left( 1+2^{k-1}\right) =\dfrac{2^{k}}{k}+\underbrace{\dfrac
{2^{k}}{k}\cdot2^{k-1}}\_{=\dfrac{2^{2k-1}}{k}=\dfrac{2^{2k}}{2k}}=\dfrac
{2^{k}}{k}+\dfrac{2^{2k}}{2k},
\end{align\*}
this rewrites as $v\_{3}\left( \dfrac{2^{k}}{k}+\dfrac{2^{2k}}{2k}\right)
=-v\_{3}\left( k\right) $. This proves Lemma 3 **(b)**. $\blacksquare$



> 
> **Lemma 4.** Let $n$ be a positive integer. Let $m$ be the largest nonnegative
>  integer such that $n\geq3^{m}$. Set
>  \begin{align\*}
> a=\sum\limits\_{\substack{k\in\left\{ 1,2,\ldots,n\right\} ;\\3^{m}\nmid k}
> }\dfrac{2^{k}}{k}\qquad\text{and}\qquad b=\sum\limits\_{\substack{k\in\left\{
> 1,2,\ldots,n\right\} ;\\3^{m}\mid k}}\dfrac{2^{k}}{k}.
> \end{align\*}
>  Then:
> 
> 
> **(a)** We have $v\_{3}\left( a\right) >-m$.
> 
> 
> **(b)** We have $v\_{3}\left( b\right) =-m$.
> 
> 
> 


*Proof of Lemma 4.* **(a)** Define a subset $G$ of $\mathbb{Q}$ by
\begin{align\*}
G=\left\{ r\in\mathbb{Q}\ \mid\ v\_{3}\left( r\right) >-m\right\} .
\end{align\*}
Then, $0\in G$ (since $v\_{3}\left( 0\right) =\infty>-m$).


Next, we shall show that the set $G$ is closed under addition. Indeed, let
$s,t\in G$. Then, $s\in G=\left\{ r\in\mathbb{Q}\ \mid\ v\_{3}\left(
r\right) >-m\right\} $; in other words, $s\in\mathbb{Q}$ and $v\_{3}\left(
s\right) >-m$. Likewise, $t\in\mathbb{Q}$ and $v\_{3}\left( t\right) >-m$.
Both numbers $v\_{3}\left( s\right) $ and $v\_{3}\left( t\right) $ are $>-m$
(since $v\_{3}\left( s\right) >-m$ and $v\_{3}\left( t\right) >-m$). Thus,
$\min\left\{ v\_{3}\left( s\right) ,v\_{3}\left( t\right) \right\} >-m$
(since $\min\left\{ v\_{3}\left( s\right) ,v\_{3}\left( t\right) \right\}
$ is one of these two numbers $v\_{3}\left( s\right) $ and $v\_{3}\left(
t\right) $). Now, Proposition 1 **(b)** (applied to $3$, $s$ and $t$ instead
of $p$, $a$ and $b$) yields $v\_{3}\left( s+t\right) \geq\min\left\{
v\_{3}\left( s\right) ,v\_{3}\left( t\right) \right\} >-m$. In other words,
$s+t\in G$ (by the definition of $G$). Now, forget that we fixed $s,t$. We
thus have proven that $s+t\in G$ for all $s,t\in G$. In other words, the set
$G$ is closed under addition. Hence, $G$ is a submonoid of the additive monoid
$\left( \mathbb{Q},+\right) $ (since $0\in G$). Thus, any finite sum of
elements of $G$ is an element of $G$.


Now, let $k\in\left\{ 1,2,\ldots,n\right\} $ be such that $3^{m}\nmid k$.
Proposition 1 **(d)** (applied to $3$, $m$ and $k$ instead of $p$, $i$ and
$n$) shows that we have the equivalence $\left( 3^{m}\mid k\right)
\ \Longleftrightarrow\ \left( v\_{3}\left( k\right) \geq m\right) $. Thus,
we do not have $v\_{3}\left( k\right) \geq m$ (since we do not have
$3^{m}\mid k$ (because $3^{m}\nmid k$)). In other words, we have $v\_{3}\left(
k\right) <m$. But Lemma 3 **(a)** yields $v\_{3}\left( \dfrac{2^{k}}
{k}\right) =-\underbrace{v\_{3}\left( k\right) }\_{<m}>-m$. In other words,
$\dfrac{2^{k}}{k}\in G$ (by the definition of $G$).


Forget that we fixed $k$. We thus have shown that $\dfrac{2^{k}}{k}\in G$ for
each $k\in\left\{ 1,2,\ldots,n\right\} $ satisfying $3^{m}\nmid k$. In other
words, all addends in the sum $\sum\limits\_{\substack{k\in\left\{ 1,2,\ldots
,n\right\} ;\\3^{m}\nmid k}}\dfrac{2^{k}}{k}$ belong to $G$. Hence,
$\sum\limits\_{\substack{k\in\left\{ 1,2,\ldots,n\right\} ;\\3^{m}\nmid k}
}\dfrac{2^{k}}{k}$ is a finite sum of elements of $G$, and thus must be an
element of $G$ itself (since any finite sum of elements of $G$ is an element
of $G$). In other words, $\sum\limits\_{\substack{k\in\left\{ 1,2,\ldots,n\right\}
;\\3^{m}\nmid k}}\dfrac{2^{k}}{k}\in G$. Hence, $a=\sum\limits\_{\substack{k\in
\left\{ 1,2,\ldots,n\right\} ;\\3^{m}\nmid k}}\dfrac{2^{k}}{k}\in G$. In
other words, $v\_{3}\left( a\right) >-m$ (by the definition of $G$). This
proves Lemma 4 **(a)**.


**(b)** We are in one of the following two cases:


*Case 1:* We have $2\cdot3^{m}\leq n$.


*Case 2:* We have $2\cdot3^{m}>n$.


Let us first consider Case 1. In this case, we have $2\cdot3^{m}\leq n$. We
have defined $m$ to be the largest nonnegative integer such that $n\geq3^{m}$.
Thus, $n\geq3^{m}$ but $n<3^{m+1}$. Hence, $3^{m}\leq n$ and $3^{m+1}>n$.
Thus, $3^{m}\in\left\{ 1,2,\ldots,n\right\} $ (since $3^{m}\leq n$) and
$2\cdot3^{m}\in\left\{ 1,2,\ldots,n\right\} $ (since $2\cdot3^{m}\leq n$),
but $3\cdot3^{m}\notin\left\{ 1,2,\ldots,n\right\} $ (since $3\cdot
3^{m}=3^{m+1}>n$). Hence, the only multiples of $3^{m}$ that belong to the set
$\left\{ 1,2,\ldots,n\right\} $ are $3^{m}$ and $2\cdot3^{m}$. In other
words, the only $k\in\left\{ 1,2,\ldots,n\right\} $ that satisfy $3^{m}\mid
k$ are $3^{m}$ and $2\cdot3^{m}$.


But
\begin{align\*}
b=\sum\limits\_{\substack{k\in\left\{ 1,2,\ldots,n\right\} ;\\3^{m}\mid k}
}\dfrac{2^{k}}{k}=\dfrac{2^{3^{m}}}{3^{m}}+\dfrac{2^{2\cdot3^{m}}}{2\cdot
3^{m}}
\end{align\*}
(since the only $k\in\left\{ 1,2,\ldots,n\right\} $ that satisfy $3^{m}\mid
k$ are $3^{m}$ and $2\cdot3^{m}$). Hence,
\begin{align\*}
v\_{3}\left( b\right) =v\_{3}\left( \dfrac{2^{3^{m}}}{3^{m}}+\dfrac
{2^{2\cdot3^{m}}}{2\cdot3^{m}}\right) =-v\_{3}\left( 3^{m}\right)
\end{align\*}
(by Lemma 3 **(b)**, applied to $k=3^{m}$), since $3^{m}$ is odd. Thus,
\begin{align\*}
v\_{3}\left( b\right) =-\underbrace{v\_{3}\left( 3^{m}\right) }\_{=m}=-m.
\end{align\*}
Hence, Lemma 4 **(b)** is proven in Case 1.


Let us next consider Case 2. In this case, we have $2\cdot3^{m}>n$. Thus,
$3^{m}\in\left\{ 1,2,\ldots,n\right\} $ (since $3^{m}\leq n$), but
$2\cdot3^{m}\notin\left\{ 1,2,\ldots,n\right\} $ (since $2\cdot3^{m}>n$).
Hence, the only multiple of $3^{m}$ that belongs to the set $\left\{
1,2,\ldots,n\right\} $ is $3^{m}$. In other words, the only $k\in\left\{
1,2,\ldots,n\right\} $ that satisfies $3^{m}\mid k$ is $3^{m}$.


But
\begin{align\*}
b=\sum\limits\_{\substack{k\in\left\{ 1,2,\ldots,n\right\} ;\\3^{m}\mid k}
}\dfrac{2^{k}}{k}=\dfrac{2^{3^{m}}}{3^{m}}
\end{align\*}
(since the only $k\in\left\{ 1,2,\ldots,n\right\} $ that satisfies
$3^{m}\mid k$ is $3^{m}$). Hence,
\begin{align\*}
v\_{3}\left( b\right) =v\_{3}\left( \dfrac{2^{3^{m}}}{3^{m}}\right)
=-v\_{3}\left( 3^{m}\right)
\end{align\*}
(by Lemma 3 **(a)**, applied to $k=3^{m}$). Thus,
\begin{align\*}
v\_{3}\left( b\right) =-\underbrace{v\_{3}\left( 3^{m}\right) }\_{=m}=-m.
\end{align\*}
Hence, Lemma 4 **(b)** is proven in Case 2.


We have now proven Lemma 4 **(b)** in both Cases 1 and 2. Hence, Lemma 4
**(b)** always holds. $\blacksquare$



> 
> **Theorem 5.** Let $n$ be a positive integer. Let $m$ be the largest
>  nonnegative integer such that $n\geq3^{m}$. Then,
>  \begin{align\*}
> v\_{3}\left( \sum\limits\_{k=1}^{n}\dfrac{2^{k}}{k}\right) =-m.
> \end{align\*}
> 
> 
> 


*Proof of Theorem 5.* Define $a$ and $b$ as in Lemma 4. Then, Lemma 4 **(a)**
yields $v\_{3}\left( a\right) >-m$, but Lemma 4 **(b)** yields $v\_{3}\left(
b\right) =-m$. Thus, $v\_{3}\left( a\right) >-m=v\_{3}\left( b\right) $.
Hence, Proposition 1 **(e)** (applied to $p=3$) yields $v\_{3}\left(
a+b\right) =v\_{3}\left( b\right) =-m$.


But each $k\in\left\{ 1,2,\ldots,n\right\} $ satisfies either $3^{m}\nmid k$
or $3^{m}\mid k$ (but not both at the same time). Hence, we can split the sum
$\sum\limits\_{k=1}^{n}\dfrac{2^{k}}{k}$ as follows:
\begin{align\*}
\sum\limits\_{k=1}^{n}\dfrac{2^{k}}{k}=\underbrace{\sum\limits\_{\substack{k\in\left\{
1,2,\ldots,n\right\} ;\\3^{m}\nmid k}}\dfrac{2^{k}}{k}}
\_{\substack{=a\\\text{(by the definition of }a\text{)}}}+\underbrace{\sum\limits
\_{\substack{k\in\left\{ 1,2,\ldots,n\right\} ;\\3^{m}\mid k}}\dfrac{2^{k}
}{k}}\_{\substack{=b\\\text{(by the definition of }b\text{)}}}=a+b.
\end{align\*}
Therefore,
\begin{align\*}
v\_{3}\left( \sum\limits\_{k=1}^{n}\dfrac{2^{k}}{k}\right) =v\_{3}\left( a+b\right)
=-m.
\end{align\*}
This proves Theorem 5. $\blacksquare$



> 
> **Corollary 6.** Let $n\in\mathbb{N}$. Then:
> 
> 
> **(a)** We have
>  \begin{align\*}
> v\_{3}\left( \sum\limits\_{k=0}^{n}\dfrac{1}{\dbinom{n}{k}}\right) \leq0.
> \end{align\*}
> 
> 
> **(b)** Assume that $\sum\limits\_{k=0}^{n}\dfrac{1}{\dbinom{n}{k}}=\dfrac{s}{t}$ for
>  two coprime integers $s$ and $t$ satisfying $t\neq0$. Then, $3\nmid s$.
> 
> 
> 


*Proof of Corollary 6.* **(a)** Let $m$ be the largest nonnegative integer
such that $n+1\geq3^{m}$. Then, $n+1\geq3^{m}$ but $n+1<3^{m+1}$.


If we had $3^{m+1}\mid n+1$, then we would have $3^{m+1}\leq n+1$ (since
$3^{m+1}$ and $n+1$ are positive integers), which would contradict
$n+1<3^{m+1}$. Hence, we do not have $3^{m+1}\mid n+1$.


Theorem 1 **(d)** (applied to $3$, $m+1$ and $n+1$ instead of $p$, $i$ and
$n$) yields the equivalence $\left( 3^{m+1}\mid n+1\right)
\ \Longleftrightarrow\ \left( v\_{3}\left( n+1\right) \geq m+1\right) $.
Hence, we do not have $v\_{3}\left( n+1\right) \geq m+1$ (since we do not
have $3^{m+1}\mid n+1$). In other words, we have $v\_{3}\left( n+1\right)
<m+1$. Thus, $v\_{3}\left( n+1\right) \leq m$ (since $v\_{3}\left(
n+1\right) $ and $m$ are integers).


Proposition 2 yields
\begin{align\*}
\sum\limits\_{k=0}^{n}\dfrac{1}{\dbinom{n}{k}}=\dfrac{n+1}{2^{n+1}}\sum\limits\_{k=1}
^{n+1}\dfrac{2^{k}}{k}.
\end{align\*}
Multiplying both sides of this equality by $\dfrac{2^{n+1}}{n+1}$, we obtain
\begin{align\*}
\dfrac{2^{n+1}}{n+1}\sum\limits\_{k=0}^{n}\dfrac{1}{\dbinom{n}{k}}=\dfrac{2^{n+1}
}{n+1}\cdot\dfrac{n+1}{2^{n+1}}\sum\limits\_{k=1}^{n+1}\dfrac{2^{k}}{k}=\sum\limits
\_{k=1}^{n+1}\dfrac{2^{k}}{k}.
\end{align\*}
Thus,
\begin{align\*}
v\_{3}\left( \dfrac{2^{n+1}}{n+1}\sum\limits\_{k=0}^{n}\dfrac{1}{\dbinom{n}{k}
}\right) =v\_{3}\left( \sum\limits\_{k=1}^{n+1}\dfrac{2^{k}}{k}\right) =-m
\end{align\*}
(by Theorem 5, applied to $n+1$ instead of $n$).


But Lemma 3 **(a)** (applied to $k=n+1$) yields
\begin{align\*}
v\_{3}\left( \dfrac{2^{n+1}}{n+1}\right) =-\underbrace{v\_{3}\left(
n+1\right) }\_{\leq m}\geq-m.
\end{align\*}
Now, Proposition 1 **(a)** (applied to $p=3$, $a=\dfrac{2^{n+1}}{n+1}$ and
$b=\sum\limits\_{k=0}^{n}\dfrac{1}{\dbinom{n}{k}}$) yields
\begin{align\*}
v\_{3}\left( \dfrac{2^{n+1}}{n+1}\sum\limits\_{k=0}^{n}\dfrac{1}{\dbinom{n}{k}
}\right) & =\underbrace{v\_{3}\left( \dfrac{2^{n+1}}{n+1}\right) }
\_{\geq-m}+v\_{3}\left( \sum\limits\_{k=0}^{n}\dfrac{1}{\dbinom{n}{k}}\right) \\
& \geq-m+v\_{3}\left( \sum\limits\_{k=0}^{n}\dfrac{1}{\dbinom{n}{k}}\right) .
\end{align\*}
Hence,
\begin{align\*}
-m+v\_{3}\left( \sum\limits\_{k=0}^{n}\dfrac{1}{\dbinom{n}{k}}\right) \leq
v\_{3}\left( \dfrac{2^{n+1}}{n+1}\sum\limits\_{k=0}^{n}\dfrac{1}{\dbinom{n}{k}
}\right) =-m.
\end{align\*}
Adding $m$ to both sides of this inequality, we find
\begin{align\*}
v\_{3}\left( \sum\limits\_{k=0}^{n}\dfrac{1}{\dbinom{n}{k}}\right) \leq0.
\end{align\*}
This proves Corollary 6 **(a)**.


**(b)** We have $\dfrac{s}{t}=\sum\limits\_{k=0}^{n}\dfrac{1}{\dbinom{n}{k}}$ and thus
$v\_{3}\left( \dfrac{s}{t}\right) =v\_{3}\left( \sum\limits\_{k=0}^{n}\dfrac
{1}{\dbinom{n}{k}}\right) \leq0$ (by Corollary 6 **(a)**). Hence, Proposition
1 **(f)** (applied to $p=3$) yields $3\nmid s$. This proves Corollary 6
**(b)**. $\blacksquare$


