Show that $\sqrt{1+t}$ lies in $\mathbb{Z}[1/2][\![t]\!]$

Here is an interesting (I thought) question:

Show that $\sqrt{1+t}$ lies in $\mathbb{Z}[1/2][\![t]\!]$

That is, let $f(t)=\sum_{k \ge 0} a_k t^k \in \mathbb{Q}[\![t]\!]$ be the unique power series with $f(t)^2=1+t$ and $f(0)=1$, and show that each $a_k$ is of the form $b/2^m$ for $b,m \in \mathbb{Z}$.

Naively I just want to "compare coefficients". That is

$$\begin{align} f(t)^2 &= (a_0+a_1t+a_2 t^2 + \cdots)(a_0+a_1t+a_2 t^2 + \cdots) \\ &= a_0^2 + (2a_0 a_1)t + \cdots \\ &= 1 + t \end{align}$$

Thus given knowledge of $a_k$ it should, in principle, be possible to determine $a_{k+1}$ via $\sum_{i+j=k+1}a_i a_j=0$, but this didn't seem to work out that well.

In fact the question tells you (one method) to do it - show that $a_k = b_{k-1} + b_k$ where $b_k = \binom{2k}{k}/(-4)^k$. I'm not quite sure how I should do that. Induction seems to be the obvious approach. Recalling that $\sum_{i+j=k+1}a_i a_j=0$ one then inductively knows all terms apart from $a_{k+1}$, but I couldn't figure out how to manipulate the $b_k$'s appropriately.

Can anyone offer any hints?

Furthermore - can one extend this method to show that $(1+t)^{1/n}$ lies in $\mathbb{Z}[1/n][\![t]\!]$?

The power series for $(1+t)^{1/n}$ is $\sum_{k \geq 0} \binom{1/n}{k}t^k$, where $\binom{a}{k} = \frac{a(a-1)\cdots(a-k+1)}{k!}$ for any $a$ (not just positive integers). If $a$ is rational then $\binom{a}{k}$ is rational. Your initial question is now: why is $\binom{1/2}{k}$ a fraction with 2-power denominator?

I claim that for any rational number $a$, the only primes that could possibly appear in the denominator of $\binom{a}{k}$ are primes that appear in the denominator of $a$. (Take $a = 1/2$ to see this answers your question.) For instance, $\binom{1/3}{k}$ will have 3-power denominators, which you can visibly see happening if you look at the power series for $(1+t)^{1/3}$: $$ (1+t)^{1/3} = 1 + \frac{1}{3}t - \frac{1}{9}t^2 + \frac{5}{81}t^3 - \frac{10}{243}t^4 + \cdots. $$ The claim tells us that the denominators of coefficients of $(1+t)^{1/6}$ are products of powers of 2 and 3, so the fraction can always be written to have a denominator that is a power of 6: \begin{eqnarray*} (1+t)^{1/6} & = & 1 + \frac{1}{6}t - \frac{5}{2^3\cdot 3^2}t^2 + \frac{55}{2^4\cdot 3^4}t^3 - \frac{935}{2^7\cdot 3^5}t^4 + \cdots \\ & = & 1 + \frac{1}{6}t - \frac{15}{6^3}t^2 + \frac{55}{6^4}t^3 - \frac{8415}{6^7}t^4 + \cdots \end{eqnarray*} This answers your "Furthermore..." question in the affirmative.

To prove the claim made above, we'll prove the contrapositive: if $p$ does not appear in the denominator of $a$ then $p$ does not appear in the denominator of $\binom{a}{k}$. The main idea to be used here is $p$-adic limits and continuity. Since $a$ has no $p$ in its denominator, it is a $p$-adic integer and thus $a$ is a $p$-adic limit of a sequence of positive integers $\{b_i\}$ (e.g., use as that sequence $\{b_i\}$ the truncations of the $p$-adic expansion of $a$ in the $p$-adic integers). The polynomial function $\binom{x}{k} \in {\mathbf Q}[x]$ is continuous in the $p$-adic topology, so from $a = \lim_{i \rightarrow \infty} b_i$ we get $\binom{a}{k} = \lim_{i \rightarrow \infty} \binom{b_i}{k}$. Since $b_i$ is a positive integer, $\binom{b_i}{k}$ is an integer. Therefore $\binom{a}{k}$ is a $p$-adic limit of integers, which means $\binom{a}{k}$ is a $p$-adic integer, i.e., $|\binom{a}{k}|_p \leq 1$, and that's another way of saying there is no $p$ in the denominator of the fraction $\binom{a}{k}$.

I had to solve (something similar to) this for a homework assignment this past semester, so I'll post a little about how I solved it.

Suppose we have some $f=a_0+a_1t+\cdots$ such that $f^2=1+t$. Then we have the infinitely many equations \begin{align} a_0^2 &= 1\\ 2a_0a_1&=1\\ a_0a_2+a_1a_1+a_2a_0&=0\\ a_0a_3+a_1a_2+a_2a_1+a_3a_0&=0\\ \vdots\\ \sum_{i=0}^{j}a_ia_{j-i} &= 0\\ \vdots \end{align}

Obvious choices for $a_0$ and $a_1$ are 1 and 1/2. As you mentioned in your original post, knowing $a_i$ for $i=0,1\dots,n$ gives you knowledge of $a_{n+1}$, so (starting over) defining $a_0=1,\,a_1=1/2,$ and $$ a_n=-\frac{1}{2}\sum_{k=1}^{n-1}a_ka_{n-k} $$ (which is just the $(n+1)$th equation above solved for $a_n$) sets you up for an easy inductive proof that $f^2=t+1$.

Hint: From the binomial series we get $$ \sqrt{1+t}=1+\frac t2+\sum_{k=2}^\infty(-1)^{k+1}\frac{1\cdot3\cdot5\cdots(2k-3)}{2\cdot4\cdot6\cdots(2k)}t^k. $$

Your question asks you to prove that all the coefficients are of the form $a(1/2)^\ell$ for some integers $a,\ell$. This is not too difficult, but not entirely obvious. So my hint is: First replace $t$ with $4t$ above (i.e. looking at the series of $\sqrt{1+4t}$ instead). It turns out that then the coefficients become integers. That is not obvious either, but looking for information about Catalan numbers should get you going. But why does that solve your problem?