"The first thing you have to be able to do is express the thing you’re trying to prove as a predicate about natural numbers. In other words, you need to form a predicate that has one input, which is a natural number. You’re setting yourself up to prove that the predicate is true for all natural numbers. (Or at least, all natural numbers of at least a certain size.) Suppose I want to prove that in the state of Virginia, all legal drinkers can vote. Then I could say “let Vote(n) be the proposition that a citizen of age n can vote.” If I want to prove an algebraic identity, like ∑ i=1 to x i = x(x+1)/2, then I have to figure out which variable is the one that needs to vary across the natural numbers. In this case it’s the x variable in my equation. So I’ll say “let P(n) be the proposition that ∑ i=1 to n i = n(n+1)/2.” (The choice of the letter “n” isn’t important here — it just needs to be a letter that stands for a number. We could have chosen anything, even sticking with x. Later, we’ll use “k” as a stand-in, so keep your eyes peeled for that.) If I want to prove that the number of leaves in a perfect binary tree is one more than the number of internal nodes, I’d have to think about which quantity I can parameterize on (i.e., which quantity I can use for my n.) In this case, I’d probably use the height of the tree. I’d say “let P(n) be the proposition that the number of leaves in a perfect binary tree of height n is one more than the number of internal nodes.” These are just examples. In any case, you need to cast your proof in a form that allows you to make statements in terms of the natural numbers. Then you’re ready to begin the process of proving by induction that your predicate is true for all the natural numbers."