Q:

Proof that every odd integer is a difference of two squares

How can I use a direct proof to show that every odd integer is the difference of two squares?

A:

Just observe that $2k+1 = (k+1)^2 - k^2$.
UPDATE: On the subject of guessing. I feel something needs to be said about it. I also feel that it would be even better if someone else pitched in, maybe someone who has more experience in logic or teaching or teaching logic.
My hint expands to a proof that goes more or less like this:

We need to prove that for any integer $k$ integers $a$ and $b$ exist such that $a^2 - b^2 = 2k+1$. Take $a = k+1$ and $b=k$ and observe that indeed $2k+1 = a^2 - b^2$. QED.

The "guessing" happens when we say out of nowhere "Take $a = k+1$ and $b=k$". My point is, and I cannot stress this enough, that this kind of guessing is absolutely OK when you prove the existence of something. The best way to prove existence of an object with desired properties is to construct such an object, and guessing is the simplest one-step construction.
The foundations for this can be found in the axioms of predicate calculus. One of the axiom schemas of predicate calculus says:
$$
( \forall x \mathcal{B}(x) ) \to \mathcal{B}(t),
$$
where $x$ is any variable, $\mathcal{B}$ is any wff (well-formed formula) and $t$ is any term that is substitutable for $x$ in $\mathcal{B}$ (roughly, no variables mentioned in $t$ must be bound by quantifiers when $t$ is substituted for free occurrences of $x$ in $\mathcal{B}$).
From this axiom schema and some basic propositional calculus, one can get:
$$
\mathcal{B}(t) \to (\exists x \mathcal{B}(x)).
$$
It follows that if you prove $\mathcal{B}(t)$, you also prove $\exists x \mathcal{B}(x)$.
This can be applied directly to our problem. Look at the wff $\mathcal{B}(k, a, b)$: "$2k+1 = a^2 - b^2$". We see that statement $\mathcal{B}(k, k+1, k)$ says "$2k+1 = (k+1)^2-k^2$", and this is considered known (can be proved). Then, applying the rule above twice, we see that statement $\exists a \exists b \mathcal{B}(k, a, b)$ can also be proved, and that is exactly what we need.
Now, the exact wffs can vary depending on your framework (you could be working in set theory, or in some flavor of arithmetic, for instance), but the message stays the same. If you have proved that some specific object is "good", then you have also proved that at least one "good" object exists.

