I will answer this question with four typical examples, all different in nature:
Example 1:
Prove by induction that $n^3-n+3$ is divisible by $3$ $\forall \space n \in \mathbb{N^+}$.
For proof by induction; these are the $\color{red}{\mathrm{three}}$ steps to carry out:
Step 1: Basis Case: For $n=1 \implies n^3-n+3= 1^3-1+3=3$ which is divisible by $3$. So statement holds for $n=1$.
Step 2: Inductive Assumption: Assume statement is true for $n=k$ such that $n^3-n+3=\color{blue}{(k^3-k+3)}=\color{blue}{3p} \tag{1}$ Where $p,k \in \mathbb{N^+}$.
Step 3: Prove Statement holds for $n=k+1$ such that $$n^3-n+3=(k+1)^3-(k+1)+3$$
$$=k^3+3k^2+3k+1-k-1+3=3k^2+3k+\color{blue}{(k^3-k+3)}= 3(k^2+k)+\color{blue}{3p}=\color{#180}{3}(k^2+k+p)$$ using our inductive assumption $(1)$ the resulting expression clearly is divisible by $3$.
Hence $n^3-n+3$ is divisible by $3$ $\forall \space n \in \mathbb{N^+}$
QED.
(QED is an abbreviation of the Latin words "Quod Erat Demonstrandum" which loosely translated means "that which was to be demonstrated". It is usually placed at the end of a mathematical proof to indicate that the proof is complete). Alternatively, you can use $\fbox{}$
Example 2:
Use trigonometric identities and induction to prove that
$\left(\begin{array}{cc}
\cos \theta & -\sin \theta \\
\sin \theta & \cos \theta
\end{array} \right)^{n} =
\left(\begin{array}{cc}
\cos (n \theta) & -\sin (n\theta)\\
\sin (n \theta) & \cos (n \theta)
\end{array} \right)$
As before, for proof by induction; these are the $\color{red}{\mathrm{three}}$ steps to carry out:
Step 1: Basis Case: For $n=1 \implies$ LHS
$=\left(\begin{array}{cc}
\cos \theta & -\sin \theta \\
\sin \theta & \cos \theta
\end{array} \right)^{n}$
$=\left(\begin{array}{cc}
\cos \theta & -\sin \theta \\
\sin \theta & \cos \theta
\end{array} \right)^{1}$
$=\left(\begin{array}{cc}
\cos (1 \theta) & -\sin (1\theta)\\
\sin (1 \theta) & \cos (1 \theta)
\end{array} \right)$
$=\left(\begin{array}{cc}
\cos (\theta) & -\sin (\theta)\\
\sin ( \theta) & \cos ( \theta)
\end{array} \right)=$ RHS. So statement holds for $n=1$.
Step 2: Inductive Assumption: Assume statement is true for $n=k$ such that
$\left(\begin{array}{cc}
\cos \theta & -\sin \theta \\
\sin \theta & \cos \theta
\end{array} \right)^{n}$
$=\left(\begin{array}{cc}
\cos \theta & -\sin \theta \\
\sin \theta & \cos \theta
\end{array} \right)^{k}$
$=\left(\begin{array}{cc}
\cos (k \theta) & -\sin (k\theta)\\
\sin (k \theta) & \cos (k \theta)
\end{array} \right)\tag{1}$
Step 3: Prove Statement holds for $n=k+1$ such that
$\left(\begin{array}{cc}
\cos \theta & -\sin \theta \\
\sin \theta & \cos \theta
\end{array} \right)^{n}$
$=\left(\begin{array}{cc}
\cos \theta & -\sin \theta \\
\sin \theta & \cos \theta
\end{array} \right)^{k+1}$
$=\left(\begin{array}{cc}
\cos \theta & -\sin \theta \\
\sin \theta & \cos \theta
\end{array} \right)^{k}$ $\times
\left(\begin{array}{cc}
\cos \theta & -\sin \theta \\
\sin \theta & \cos \theta
\end{array} \right)^{1}$
$=\left(\begin{array}{cc}
\cos (k \theta) & -\sin (k\theta)\\
\sin (k \theta) & \cos (k \theta)
\end{array} \right)
\times
\left(\begin{array}{cc}
\cos \theta & -\sin \theta \\
\sin \theta & \cos \theta
\end{array} \right)$
[using our inductive assumption $(1)$]
$=\left(\begin{array}{cc}
\cos\theta\cos (k \theta)-\sin\theta \sin(k\theta) & -\left(\sin \theta\cos (k \theta)+\sin (k \theta)\cos \theta\right)\\
\cos\theta\sin (k \theta)+\sin\theta \cos(k\theta) & \cos\theta\cos (k \theta)-\sin\theta \sin(k\theta)
\end{array} \right)$
$=\color{blue}{\left(\begin{array}{cc}
\cos (\theta(k+1)) & -\sin (\theta(k+1))\\
\sin (\theta(k+1)) & \cos(\theta(k+1))
\end{array} \right)}$
Where in the last step I used the fact that $$\cos(A \mp B)=\cos A \cos B \pm \sin A \sin B$$ and $$\sin(A \pm B)=\sin A \cos B \pm \cos A \sin B$$ and $\color{blue}{\mathrm{this}}$ is the same result if $n=k+1$ is substituted into the RHS of your original disposition.
Hence statement is true for all $n \in \mathbb{N}.$
QED.
Example 3:
Prove by induction that $3^{(3n+4)} + 7^{(2n+1)}$ is divisible by $11$ for all natural numbers $n$:
Step 1: Basis Case: for $n=1$: $P(1)= 3^{(3(1)+4)} + 7^{(2(1)+1)} = 2530$, which is divisible by $11$ so statement holds for $n=1$.
Step 2: Inductive Assumption: Assume statement is true for $n=k$: $P(k) =3^{(3k+4)} + 7^{(2k+1)} = 11a \implies 3^{3k+4} = \color{blue}{11a - 7^{2k+1}}$, where $a \in \mathbb{N}$
Step 3: Prove Statement holds for $n=k+1$:
$P(k+1)= 3^{3k+7} + 7^{2k+3} = 27 \cdot 3^{3k+4} + 49\cdot 7^{2k+1}\tag{1}$
Using the inductive assumption shown in $\color{blue}{\mathrm{blue}}$, $(1)$ becomes:
$27(\color{blue}{11a - 7^{2k+1}})+49\cdot 7^{2k+1}=27\cdot 11a -27\cdot 7^{2k+1}+ 49\cdot 7^{2k+1}=27\cdot 11a +2\cdot 11\cdot 7^{2k+1}=\color{red}{11}(27a+2\cdot 7^{2k+1})$
Hence $3^{3n+4} + 7^{2n+1}$ is a multiple of $\color{red}{11} \space\forall \space n\in \mathbb{N}$
QED.
Example 4:
Prove by induction that $$\sum_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6} \quad \forall \space n \in \mathbb{N}$$
Step 1: Basis Case: For $i=1$: $$\sum^{i=k}_{i=1} i^2=\frac{1(1+1)(2\times 1+1)}{6}= \frac{2\times 3}{6}=1$$ So statement holds for $i=1$.
Step 2: Inductive Assumption: Assume statement is true for $i=k$:
$$\sum^{i=k}_{i=1} i^2=\frac{k(k+1)(2k+1)}{6} $$
Step 3: Prove Statement holds for $i=k+1$. You need to prove that for $i=k+1$: $$\sum^{i=k+1}_{i=1} i^2=\color{blue}{\frac{(k+1)(k+2)(2k+3)}{6}}$$
To do this you cannot use: $$\sum^{i=k}_{i=n} i^2=\color{red}{\frac{n(n+1)(2n+1)}{6}} $$ as this is what you are trying to prove.
So what you do instead is notice that:
$$\sum^{i=k+1}_{i=1} i^2= \underbrace{\frac{k(k+1)(2k+1)}{6}}_{\text{sum of k terms}} + \underbrace{(k+1)^2}_{\text{(k+1)th term}}$$
$$\sum^{i=k+1}_{i=1} i^2= \frac{k(k+1)(2k+1)}{6}+\frac{6(k+1)^2}{6}$$
$$\sum^{i=k+1}_{i=1} i^2= \frac{(k+1)\left(k(2k+1)+6(k+1)\right)}{6}$$
$$\sum^{i=k+1}_{i=1} i^2= \frac{(k+1)(2k^2+\color{green}{7k}+6)}{6}=\frac{(k+1)(2k^2+\color{green}{4k+3k}+6)}{6}=\frac{(k+1)\left(2k(k+2)+3(k+2)\right)}{6}=\color{blue}{\frac{(k+1)(k+2)(2k+3)}{6}}\quad \forall \space k,n \in \mathbb{N} \quad\fbox{}$$
Which is the relation we set out to prove. So the method is to substitute $i=k+1$ into the formula you are trying to prove and then use the inductive assumption to recover the $\color{blue}{\mathrm{blue}}$ equation at the end.
Observe that in the part marked $\color{green}{\mathrm{green}}$ $7k$ has simply been rewritten as $4k+3k$. From then on you simply take out common factors.
Note that this method is only valid when you have two numbers whose product is $12$ and sum is $7$.
Or, put in another way for the general quadratic $ax^2 +bx +c$, this inspection method is only valid iff you can find two numbers whose product is $ac$ and sum is $b$.
Did I translate this correctly?
No. The oddness needs to be quantified too.
You want $\forall n~\big(\exists k~(n=2k+1)~\to~\exists k~\exists l~(n=k^2-l^2)\big)$
It might be helpful to emphasise that the existance establishing oddness is distinct from the existances establishing sum-of-squares.
$$\forall n~\big(\exists k~(n=2k+1)~\to~\exists a~\exists b~(n=a^2-b^2)\big)$$
In my initial universal quantifier, I sometimes see people write $∀n∈S P(n)$. Is this just another way of specifying the domain so I don't have to say what the domain is after writing everything down in symbols? A kind of shorthand?
You may wish to explicitly indicate the domain of the discussion.
$$\forall n\in\Bbb Z~\big(\exists k\in\Bbb Z~(n=2k+1)~\to~\exists a\in\Bbb Z~\exists b\in\Bbb Z~(n=a^2-b^2)\big)$$
As you see, this can clutter the statement when every entity is drawn from the same domain. So if you have established in accompanying text that is the implicit domain is the Integers, there is no need to explicitly indicate it in the statement.
In the book I use they'll nest quantifiers explicitly like $∃k~∃l~Q(k,l)$. In my translation I did what I've seen elsewhere which is to do $∃~k,l~Q(k,l)$ is this okay?
It is a style choice. I prefer explictly quantifying each variable, but again, abbreviating things can reduce clutter
And if the answer to Question 2 above was that using the $∈$ shorthand is acceptable, then I'm guessing I could also write this as $∃~k,l~∈S~Q(k,l)$.
It ... is accepted, as long as you take care to avoid ambiguity.
I know to begin working on a universally quantified statement I can invoke universal instantiation. My book defines this as $∀x~P(x)~∴~P(c)$. It then goes on with an example of a formal proof using this on the form $∀x~(P(x)⟹Q(x))~∴~P(a)⟹Q(a)$. How are they applying Universal Instantiation across the $⟹$, when the definition only has a single predicate $P(x)$? Is it that they've set $P(x)$ to mean $P(x)⟹Q(x)$?
Yes, you substitute $c$ for $x$ everywhere in the scope of the quantification. Here that is $(P(x)\to Q(x))$. In Universal Elimination (or Instantiation) you are deducing that if something is true about the universal bound variable $x$, then it will be true for an unbound variable $c$. (Or $a$ or whatever.)
Finally, for direct proof we assume the antecedent is true and try to deduce the consequent. But, doesn't this create the same problem as above? Begging the question that is. Say I have $∀x(P(x)⟹Q(x))$. Then I use direct proof to assume $P(x)$ is true. Well wouldn't I use Universal instantiation here and have
$P(a)$, then using Universal Modus Ponens I could automatically infer
$Q(a)$ is true?
No. If $∀x~(P(x)\to Q(x))$ is what you are trying to prove, then you don't have it. You cannot assert that a conclusion is proven inside its own proof.
Your argument should go: Let $a$ be an arbitrary term. Assume $P(a)$ and derive $Q(a)$ by some valid logic. Thus deducing that $P(a)\to Q(a)$, and since $a$ is arbitrary therefore, by Universal Generalisation, $\forall x~(P(x)\to Q(x))$.
In this case:
Let $m$ be an arbitrary integer, and assume there exists some integer $c$ such that $m=2c+1$. Since for any $c$, $(c+1)^2=c^2+2c+1$ thus $m=(c+1)^2-c^2$.
Therefore: If an integer is odd, then it is the difference of the squares for two integers.
$$\def\fitch#1#2{\begin{array}{|l}#1 \\\hline #2\end{array}}
\fitch{}{\fitch{[m]}{\fitch{\exists k~(m=2k+1)}{\fitch{[b]~m=2b+1}{\fitch{[a]~ b+1}{a^2=b^2+2b+1\\a^2=b^2+m\\m=a^2-b^2\\\exists l~(m=a^2-l^2)\\\exists k~\exists l~(m=k^2-l^2)}\\\exists k~\exists l~(m=k^2-l^2)}\\\exists k~\exists l~(m=k^2-l^2)}\\\exists k~(m=2k+1)\to\exists k~\exists l~(m=k^2-l^2)}\\\forall n~(\exists k~(n=2k+1)\to\exists k~\exists l~(n=k^2-l^2))}$$
Time out ... that's enough for now ... maybe more to come later ...
Best Answer
It’s possible that your proofs are too wordy and don’t use enough notation, but even if that’s true, what you’re proposing here is not the solution: arguments expressed almost entirely in formal logical notation are at least as hard to read as arguments that drown the reader in verbiage. Of course you want to be sure that what you write is correct, but after that the most important thing is saying it clearly. Generally that requires a well-chosen mixture of symbols and words; the ideal mixture is different for different people, but for most people both extremes are hard to read. Here’s an example, modified from an earlier question, of three ways of defining a certain function:
Define a function $f$ by $$f:\wp(\Bbb N)\setminus\{\varnothing\}\to\Bbb N \\ x\mapsto y \owns y\in x\land\forall z:z\in x\to z\geq y\;.$$
Define a function $f$ by $$f:\wp(\Bbb N)\setminus\{\varnothing\}\to\Bbb N:x\mapsto\min x\;.$$
Given a nonempty set $A$ of natural numbers, denote its least element by $f(A)$.
The first is horrible to read. The second is much clearer and would be appropriate wherever a concise but readable definition is wanted. And the third, though by far the most wordy, is instantly clear. I would never use the first; the choice between the second and third would depend on the context and the intended audience. When writing for your professor, for instance, you might want to lean towards the second version.
Besides tending to make mathematics hard to read, excessive use of formal notation can get in the way of thinking about a problem. For a possible example of this phenomenon, see this question and my answer to it.
Please note that I do not mean to deny the possibility that you really are muddying things by using words when symbols would be preferable: a version of the quadratic formula and its derivation that used no mathematical symbols would be extremely hard to follow.
Because judgement of readability is highly subjective, it’s very difficult to give concrete, objective advice. The best that I can suggest is to pay attention to the way proofs are written in textbooks; you’ll find considerable variation, but in general it will be within the range of acceptable practice, especially in your more advanced courses.