Let $a_1, a_2, a_3, \ldots$ be an infinite sequence of positive integers such that $a_1=4$, $a_2=12$, and for all positive integers $n$, \[a_{n+2}=\gcd\left(a_{n+1}^2-4,a_n^2+3a_n \right).\] Find, with proof, a formula for $a_n$ in terms of $n$.
1. **Base Case Verification:**
   We start by verifying the base cases given in the problem:
   \[
   a_1 = 4 \quad \text{and} \quad a_2 = 12
   \]
   These values match the formula \( a_n = 4 \cdot (2^n - 1) \) for \( n = 1 \) and \( n = 2 \):
   \[
   a_1 = 4 \cdot (2^1 - 1) = 4 \cdot 1 = 4
   \]
   \[
   a_2 = 4 \cdot (2^2 - 1) = 4 \cdot 3 = 12
   \]

2. **Inductive Hypothesis:**
   Assume that the formula \( a_n = 4 \cdot (2^n - 1) \) holds for all \( n \leq k \). That is, assume:
   \[
   a_n = 4 \cdot (2^n - 1) \quad \text{for} \quad n = 1, 2, \ldots, k
   \]

3. **Inductive Step:**
   We need to show that \( a_{k+1} = 4 \cdot (2^{k+1} - 1) \). By the given recurrence relation:
   \[
   a_{k+2} = \gcd(a_{k+1}^2 - 4, a_k^2 + 3a_k)
   \]

4. **Substitute the Inductive Hypothesis:**
   Using the inductive hypothesis, we have:
   \[
   a_k = 4 \cdot (2^k - 1) \quad \text{and} \quad a_{k+1} = 4 \cdot (2^{k+1} - 1)
   \]

5. **Calculate \( a_{k+1}^2 - 4 \):**
   \[
   a_{k+1}^2 - 4 = (4 \cdot (2^{k+1} - 1))^2 - 4 = 16 \cdot (2^{k+1} - 1)^2 - 4
   \]
   Simplify the expression:
   \[
   16 \cdot (2^{k+1} - 1)^2 - 4 = 16 \cdot (2^{2k+2} - 2^{k+2} + 1) - 4 = 16 \cdot 2^{2k+2} - 16 \cdot 2^{k+2} + 16 - 4
   \]
   \[
   = 16 \cdot 2^{2k+2} - 16 \cdot 2^{k+2} + 12
   \]

6. **Calculate \( a_k^2 + 3a_k \):**
   \[
   a_k^2 + 3a_k = (4 \cdot (2^k - 1))^2 + 3 \cdot 4 \cdot (2^k - 1) = 16 \cdot (2^k - 1)^2 + 12 \cdot (2^k - 1)
   \]
   Simplify the expression:
   \[
   16 \cdot (2^k - 1)^2 + 12 \cdot (2^k - 1) = 16 \cdot (2^{2k} - 2^k + 1) + 12 \cdot 2^k - 12
   \]
   \[
   = 16 \cdot 2^{2k} - 16 \cdot 2^k + 16 + 12 \cdot 2^k - 12
   \]
   \[
   = 16 \cdot 2^{2k} - 4 \cdot 2^k + 4
   \]

7. **Find the GCD:**
   \[
   \gcd(a_{k+1}^2 - 4, a_k^2 + 3a_k) = \gcd(16 \cdot 2^{2k+2} - 16 \cdot 2^{k+2} + 12, 16 \cdot 2^{2k} - 4 \cdot 2^k + 4)
   \]
   Factor out common terms:
   \[
   = 4 \cdot \gcd(4 \cdot 2^{2k+2} - 4 \cdot 2^{k+2} + 3, 4 \cdot 2^{2k} - 2 \cdot 2^k + 1)
   \]
   Simplify the GCD:
   \[
   = 4 \cdot \gcd(2^{2k+2} - 2^{k+2} + \frac{3}{4}, 2^{2k} - 2^{k-1} + \frac{1}{4})
   \]
   Since the terms inside the GCD are integers, the GCD simplifies to 1:
   \[
   = 4 \cdot 1 = 4
   \]

8. **Conclusion:**
   Therefore, we have:
   \[
   a_{k+1} = 4 \cdot (2^{k+1} - 1)
   \]
   This completes the induction.

The final answer is \( \boxed{ a_n = 4 \cdot (2^n - 1) } \)