It helps to explicitly visualize people who I perceive as being skilled in X failing at it over and over again
Some of the greatest value I’ve gotten out of attending math lectures comes from seeing math Ph.Ds (particularly good ones) make mistakes or even forget exactly how a proof works and have to dismiss class early. It never happened often, but just often enough to keep me from getting discouraged.
Lemma: sum of the degrees of the nodes is twice the number of edges.
Proof: We proceed by induction on the number of edges. If a graph has 0 edges, the the sum of degrees of edges is 0=2(0). Now, by way of induction, assume, for all graphs with n edges, the sum of the degrees of the nodes 2n; we wish to show that, for all graphs with n+1 edges, the sum of the degrees of the nodes is 2(n+1). But the sum of the degrees of the nodes is (2n)+2 = 2(n+1). ∎
The theorem follows as a corollary.
If you want practice proving things and haven’t had much experience so far, I’d recommend Mathematics for Computer Science, a textbook from MIT and distributed under a free license, along with the associated video lectures *. To use Terry Tao’s words, Sipser is writing at both level 1 and 3: he’s giving arguments an experienced mathematician is capable of filling in the details to form a rigorous argument, but also doing so in such a way that a level 1 mathematician can follow along. Critically, however, from what I understand from reading Sipser’s preface, he’s definitely not writing a book to move level 1 mathematicians to level 2, which is a primary goal of the MIT book. If you’re looking to prove things because you haven’t done it much before, I infer you’re essentially looking to transition from level 1 to 2, hence the recommendation.
A particular technique I picked up from the MIT book, which I used here, was that, for inductive proofs, it’s often easier to prove a stronger theorem, since it gives you stronger assumptions in the inductive step.
PM me if you want someone to look over your solutions (either for Sipser or the MIT book). In the general case, I’m a fan learning from textbooks and believe that working things out for yourself without being helped by an instructor makes you stronger, but I’m also convinced that you need feedback from a human when you’re first getting learning how to prove things.
* The lectures follow an old version of the book, which ~350 pages shorter and, crucially, lacks exercises.