(I) From the given, we have $a_{n+1} = \frac{2a_n - 1}{a_n} = 2 - \frac{1}{a_n}$. Since $a_1=1$, we calculate the first few terms:
$a_2 = 2 - \frac{1}{2} = \frac{3}{2}$,
$a_3 = 2 - \frac{2}{3} = \frac{4}{3}$,
$a_4 = 2 - \frac{3}{4} = \frac{5}{4}$.

From this pattern, we can conjecture that $a_n = \frac{n+1}{n}$.

To prove, consider the following:
1. Base case: When $n=1$, $a_1=1=\frac{2}{1}$. Therefore, the conjecture is correct.
2. Inductive step: Assume that for $n=k$ (where $k \ge 1$, $k \in \mathbb{Z}$), the conjecture holds, i.e., $a_k = \frac{k+1}{k}$. Then,
$$a_{k+1} = 2 - \frac{1}{a_k} = 2 - \frac{k}{k+1} = \frac{k+2}{k+1} = \frac{(k+1)+1}{k+1},$$
which implies the conjecture holds for $n=k+1$ as well.

Combining the base case and the inductive step, we have proven that the sequence $\{a_n\}$ follows the formula $a_n = \frac{n+1}{n}$. Therefore,
$$\boxed{a_n = \frac{n+1}{n}}.$$

(II) Assume $\frac{1+a_n}{a_k} \geq 2$ and $\frac{1+a_k}{a_n} \geq 2$. Since $a_n, a_k > 0$, we have $1+a_n > 2a_n$ and $1+a_k > 2a_k$. Adding these inequalities gives us $(1+a_n) + (1+a_k) \geq 2a_n + 2a_k$, which implies $a_n + a_k \leq 2$.

However, since $a_n = \frac{n+1}{n} = 1 + \frac{1}{n} > 1$ and $a_k = \frac{k+1}{k} = 1 + \frac{1}{k} > 1$, we get $a_n + a_k > 2$, which is a contradiction.

Therefore, our assumption is false, and at least one of $\frac{1+a_n}{a_k}$ and $\frac{1+a_k}{a_n}$ must be less than 2. Hence,
$$\boxed{\text{At least one of } \frac{1+a_n}{a_k} \text{ and } \frac{1+a_k}{a_n} \text{ is less than } 2}.$$