Without loss of generality we may assume $a \ge b $ Then we've $$gcd(n^a+1, n^b +1)=gcd((n^a+1)- n^{a-b}(n^b +1) ,n^b +1)=gcd(1-n^{a-b} , n^b +1) \le gcd(n^{a-b}+1, n^b +1)=n^{gcd(a,b)} +1$$Point out mistakes if any, as I'm not completely certain of correctedness

Here is some trickery: $$\gcd(n^a+1,n^b+1)=\gcd\bigg(\frac{n^{2a}-1}{n^a-1},\frac{n^{2b}-1}{n^b-1}\bigg)=\gcd\Bigg(\frac{\prod_{d|2a}\Phi_d(n)}{\prod_{d|a}\Phi_d(n)},\frac{\prod_{d|2b}\Phi_d(n)}{\prod_{d|b}\Phi_d(n)}\Bigg)=\gcd\bigg(\prod_{d\nmid a,d|2a}\Phi_d(n),\prod_{d\nmid b,d|2b}\Phi_d(n)\bigg)=$$$$=\prod_{d\nmid a;b,d|\gcd(2a,2b)}\Phi_{d}(n)\leq \prod_{d\nmid \gcd(a,b),d|2\gcd(a,b)}\Phi_{d}(n)=\frac{\prod_{d|2\gcd(a,b)}\Phi_{d}(n)}{\prod_{d|\gcd(a,b)}\Phi_{d}(n)}=n^{\gcd(a,b)}+1$$ But why is $$\prod_{d\nmid a;b,d|\gcd(2a,2b)}\Phi_{d}(n)\leq \prod_{d\nmid \gcd(a,b),d|2\gcd(a,b)}\Phi_{d}(n)$$true? This is because $\Phi_k(n)\geq 1$ for any $k,n$ and if $$A=\{d:d\nmid a;b,d|\gcd(2a,2b)\}$$$$B=\{d:d\nmid \gcd(a,b),d|2\gcd(a,b)\}$$$$\text{then }A\subset B$$ It is clear that for the inequality to accur, we must have $A=B$. Let $a=dx$ and $b=dy$ with coprime $x$ and $y$. The following sets must be the same: $$A=\{d:d\nmid d;x;y,d|\2x\}$$$$B=\{d:d\nmid x,d|2x\}$$For this to be true, we must have $\gcd(x;d)=\gcd(y;d)=1$. Thus, indeed, there are infinitely many pairs for which equality is obtained (and $a\nmid b$, $b\nmid a$)

Let $n^{gcd(a, b)} = m$, $a = gcd(a, b)x$, and $b = gcd(a, b)y$. Then it suffices to prove that $gcd(m^x + 1, m^y + 1) \leq m + 1$ where $m, x, y$ are positive integers and $(x, y) = 1$. Let $d = gcd(m^x + 1, m^y + 1)$, then we have $m^x \equiv m^y \equiv -1 \pmod{d}$. By Bezout's identity, there exists integers $p, q$ so that $px + qy = 1$, so we also have $m = m^{px+qy} \equiv \pm 1 \pmod{d}$. If $m \equiv 1 \pmod{d}$, then $1 \equiv m^x \equiv -1 \pmod{d}$, so $d = 1$ or $d = 2$, which obviously means $d \leq 2 \leq m+1$. And if $m \equiv -1 \pmod{d}$ then $d \mid m + 1$, so $d \leq m + 1$. Hence, part (a) is proved. For part (b), take any $a, b$ that are both odd and relatively prime. Since $n + 1 \mid gcd(n^a + 1, n^b + 1)$, then by part (a) $gcd(n^a + 1, n^b + 1) = n + 1$.