Why not both true and false?

Gödel's theorem could be more accurately interpreted as saying that we can never be sure of the consistency of a sufficiently complex system. We can't be sure, for instance, that the Peano Axioms don't prove $1+1=3$. We sure hope this isn't the case, but no proof would convince us otherwise (and it's probably not, since the Peano Axioms have an intuitive model as being the natural numbers with addition and multiplication).

However, it's still true that $1+1=2$ even if the Peano Axioms say otherwise (indeed, if they proved $1+1=3$, they would also have to prove $1+1\neq 3$, and also every other statement you could possibly make within that system). In fact, we can say that, if a (suitably complex) system is inconsistent, then it admits both a proof and a disproof of every statement - this is the principle of explosion.

The difference is that there is an intended model of the Peano Axioms - the natural numbers with addition and multiplication. This is clearly well-defined and certain things are undeniably true of them. We would therefore expect that the Peano Axioms are, in fact, consistent (though we can't prove it) - and, if it is consistent, everything it proves is true and undeniably so. Even if PA were inconsistent, we would still expect proofs like the $1+2+\ldots+n=\frac{n(n+1)}2$ to be work since they are leveraging such simple properties of the structure of the natural numbers.

The point here is that "truth" and "proof" are distinct statements - but we tend to identify them because we assume our logical systems are consistent, or at least assume that the bits of them we actually use are consistent.

I have two answers for you.

One has already been said so I will only say it briefly: if we exhaustively prove something to be true, there can be no counter example - ie, in the case of an induction argument like you provided.

Second, I will answer you with Godel as well. He is mainly known for his Incompleteness Theorems (because they are far more interesting), but his first famous work was for proving his Completeness Theorem. This tell us many things, among which is that consistent and sound system will not have the counter examples you suggest may exist (to quote Wikipedia, a more general formulation would be "It says that for any first-order theory T with a well-orderable language, and any sentence S in the language of the theory, there is a formal proof of S in T if and only if S is satisfied by every model of T (S is a semantic consequence of T).").

Further, you misunderstand his Incompleteness theorems. It does not say no theory is consistent, it simply says no consistent theory can prove its own consistency. Indeed, Godel proved the consistency of Peano Arithmetic using Type Theory which could not prove it's own consistency.

However, (depending on your level) all of the theorems you encounter can be assured to be true if proven because ZFC (the most common foundation of mathematics) had it's consistency proven by only assuming the existence of a Weakly Inaccessible Cardinal. I think this is widely accepted, so if you can accept the existence of that, you are safe.

EDIT: It has been made known to me in the comments that making the existance of a Weakly Inaccessible Cardinal an axiom creates a far stronger theory than needed to prove the consistency of ZFC. In any case, the point remains that any system of mathematics you're working with has likely been proven consistent by assuming something only slightly stronger - for whatever that is worth.

It also occurs to me that first order logic includes the Law of Noncontradiction (also known as the Law of Excluded Middle) as an axiom, where this is also know to be consistent by Godel's Completeness theorem. So, with this your more general question of "Why not both true and false?" is answered because we take it as axiomatic and show that including such an axiom is consistent.

For example we can prove (e.g. by induction) that $1+2+3+\cdots+n=\frac{n(n+1)}{2}$ for all positive integers $n$. But how can we be sure that no one will ever find a counter example?

The answer to "how can we be sure that no one will ever find a counter example?" is that we can prove (e.g. by induction) that $1+2+3+\cdots+n=\dfrac{n(n+1)}{2}$ for all positive integers $n$.

P.S. "Counterexamples" of the kind whose existence is suggested by Gödel's incompleteness theorem are not in fact numbers in the sequence $1,2,3,\ldots$, that can be reached after some finite number of steps, like the number $1000$. Rather they are members of systems of "numbers" that satisfy all of the axioms within some system that admits algorithmic proof-checking.