Question about recursive formula for carry bit in modular addition mod $2^n$ I am reading a paper and there authors defined recursively the carry bit of modular addition $\mod 2^n$. Specifically, suppose we are summing $x+y=z \mod 2^n$ and suppose $C[i]$ is the carry bit of the i-th bit in $x+y$ then $C[i+1]=x[i]\cdot y[i] \oplus(x[i]\oplus y[i])\cdot C[i]$. My question is how they reach this formula? here in Section 3 other paper with the same definition.

The resulting carry is $1$ exactly if at least two of the three inputs $x$, $y$, and $c$ are $1$.  This is expressed by
$$(x \wedge y)\vee(x \wedge c) \vee (y \wedge c).$$
Now use the following identities on the ring $\mathbb Z \pmod 2$. For any $a$ and $b$:
$$\begin{eqnarray}
a+a &=& 0 \\
a^2 &=& a \\
a \vee b &=& a+b+ab \\
a \wedge b &=& ab
\end{eqnarray}$$
It turns out that the boolean expression above reduces to the surprisingly similar expression $$xy + xc + yc$$ which can be factored to get the requested expression $$xy + (x + y)c.$$
