Today I decided to binge on discrete mathematics after a three year hiatus. I tackled three proofs, and all of them required the introduction of assumptions that seemed to not be found in the givens as well as caffeine.
Out of those three proofs, I got two incorrect after contemplating for 30 minutes to an hour. Looking on at them, they make me ask the question "how on Earth would I have known to do that?"
Below is an example of what I mean:
Prove $a - b \; | \; a^n - b^n$.
Skip to induction step:
$$a^{k + 1} - b^{k + 1} = a^{k + 1} - ab^k + ab^k - b^{k + 1}$$
$$a(a^k - b^k) - b^k(a - b)$$
Which implies that
$$(a - b) \; | \; a^{k + 1} - b^{k + 1} \implies \text{True}.$$
Due to the result in form $a \; | \; b + c$ being true iff $a \; | \; b$ and $a \; | \; c$.
Basically the added assumption allows me to use both the zeroth case and the base case to prove the statement true, in a pretty elegant way. I was messing around with the power series, which would have resulted in a weaker proof if there was one there, and when this simpler solution was there the whole time.
The other proof involved inequalities between a polynomial and $2^n$, which seem to require added assumptions for most proofs in that class. In order to use the given $9 < k$ for proof of $n^3 < 2^n$, it was necessary to introduce $k^3 + 9k^3$ to demonstrate that $2k^3 < 2 \cdot 2^k \implies 2^{k+1}$. Once again, although I could understand the rationale for this move in hindsight (it kind of blew my mind), I am unsure how I could have come to that insight.
Granted I haven't effectively scaffolded my knowledge of either inequalities or divisibility. However, it seems like in both cases I needed to understand what kind of algebraic "moves" preserve the truth while introducing new information to the proof, allowing it move forward; almost like logical free lunches. But that seems to require an understanding of algebra that is more deeply developed than what I have right now, and what other textbooks have given me.
Is there a way to improve my ability to introduce the right kind of algebraically expressed number, while preserving truth and equality, to move proofs forward?
Are there algebra textbooks that deal with algebra in a more sophisticated way to improve this intuition?
A method which sometimes helps me in similar situations.
Please read this carefully, because it's very similar but significantly different from a common error in proofs.
Note: Steps 1 & 2 are only aids so we can figure out how to create the proof, but only step 3 belongs as the final answer. Step 2 will often show which magical statement like $2k^3<2⋅2^k$ will be useful.
Expanding on potato's answer, $(a-b) | (a^k-b^k)$, polynomial long divison is a more natural, straightforward proof method.
As you can see, some proofs are taught in a difficult manner, pulling statements out of thin air, etc. But thankfully sometimes much more natural proof methods apply.
Adding magic forms of zero, such as $−ab^k+ab^k$ or multiplying by magic forms of 1 are another common trick. Review how to rationalize the denominator for fractions like exercises 7 to 10 from http://www.regentsprep.org/Regents/math/algtrig/ATO3/ratdenprac.html
For proofs, over a set of statements, especially whole numbers, n, natural induction is common. Until your confident applying induction, consider writing out the base case, the inductive step; $$P_k -> P_{k+1}$$ and specify both sides of the inductive step. That is the specific $P_k$ we're allowed to assume and the specific $P_{k+1}$ we need to prove.