1. **Problem statement:** Given that $\gcd(a^n,b^n)=1$ and $\gcd(a,b^n)=1$, prove by induction that $\gcd(a^{n+1}+1,b^{n+1}+1)=1$. 2. **Base case (n=1):** We need to show $\gcd(a^{1+1}+1,b^{1+1}+1) = \gcd(a^2+1,b^2+1) = 1$. Since $\gcd(a,b^1) = \gcd(a,b) = 1$ by given, and $\gcd(a^1,b^1) = \gcd(a,b) = 1$, it follows that $a$ and $b$ are coprime. If a prime $p$ divides both $a^2+1$ and $b^2+1$, then $p$ divides their difference: $$ (a^2+1) - (b^2+1) = a^2 - b^2 = (a-b)(a+b). $$ Since $p$ divides $a^2+1$, $p$ cannot divide $a$ (otherwise $p$ divides 1, impossible). Similarly for $b$. Because $a$ and $b$ are coprime, $p$ cannot divide both $a-b$ and $a+b$ unless $p$ divides 2. But if $p=2$, then $a^2+1$ and $b^2+1$ are odd (since squares are congruent to 0 or 1 mod 4), so 2 does not divide both. Hence, no prime divides both $a^2+1$ and $b^2+1$, so $\gcd(a^2+1,b^2+1)=1$. 3. **Inductive hypothesis:** Assume for some $k \geq 1$, $\gcd(a^{k}+1,b^{k}+1) = 1$. 4. **Inductive step:** Show $\gcd(a^{k+1}+1,b^{k+1}+1) = 1$. Suppose a prime $p$ divides both $a^{k+1}+1$ and $b^{k+1}+1$. Then $p$ divides their difference: $$ (a^{k+1}+1) - (b^{k+1}+1) = a^{k+1} - b^{k+1}. $$ Factor $a^{k+1} - b^{k+1}$: $$ a^{k+1} - b^{k+1} = (a - b)(a^k + a^{k-1}b + \cdots + b^k). $$ Since $p$ divides $a^{k+1}+1$, it cannot divide $a$ (otherwise $p$ divides 1), similarly for $b$. Because $\gcd(a,b^n) = 1$ for all $n$, $p$ cannot divide $a-b$ or the sum term unless it divides 1, which is impossible. Therefore, no prime divides both $a^{k+1}+1$ and $b^{k+1}+1$, so $$ \gcd(a^{k+1}+1,b^{k+1}+1) = 1. $$ 5. **Conclusion:** By induction, for all $n \geq 1$, $$ \gcd(a^{n}+1,b^{n}+1) = 1. $$