Derive: How to Know a Claim Is True

Write $d=m+n$. Every pair lies on exactly one diagonal, because the sum of its two coordinates is a single whole number, and diagonal $d$ holds exactly $d+1$ pairs, one for each choice of $m$ from 0 to $d$ with $n=d-m$. The pairs on diagonals $0$ through $d-1$ number $1+2+\cdots +d=d(d+1)/2$, so $(m,n)$ is preceded by that many pairs and then by $m$ further pairs on its own diagonal. Counting positions from 1 gives $I(m,n)=d(d+1)/2+m+1$, which is a positive whole number.

For injectivity, note where the values of a fixed diagonal land. The pairs on diagonal $d$ receive the indices from $d(d+1)/2+1$ through $d(d+1)/2+d+1=(d+1)(d+2)/2$, which is a block of consecutive whole numbers. The blocks for consecutive diagonals meet end to end and do not overlap, so the index determines $d$; the value then determines $m=I-d(d+1)/2-1$, and $n=d-m$ follows. Two pairs with the same index therefore have the same diagonal, the same first coordinate, and the same second coordinate. For surjectivity, take any positive whole number $k$. The block endpoints $(d+1)(d+2)/2$ increase with $d$, so exactly one $d$ satisfies $d(d+1)/2<k\le (d+1)(d+2)/2$. Set $m=k-d(d+1)/2-1$, which lies between 0 and $d$, and set $n=d-m$. Then $(m,n)$ is a pair of whole numbers with $I(m,n)=k$. The map is therefore a bijection.

For $(2,3)$ the diagonal is $d=5$, the pairs before it number $15$, and $(2,3)$ is the third pair on that diagonal, so the index is $15+3=18$. The proof establishes the count and the list at once: a bijection with the positive whole numbers is a complete list, which is exactly the definition of countable in section 3.5, and the bijection is the pairing of section 3.4 with one side equal to the whole numbers. Nothing in the argument inspects the size of the sets; it reads the structure that generates the pairs.

Put $n=40+41m$ for a whole number $m$. Expanding, $$n^2+n+41=(40+41m{)}^2+(40+41m)+41=1600+3280m+1681m^2+40+41m+41.$$ Collecting the terms gives $1681m^2+3321m+1681$. Each coefficient is divisible by 41, since $1681=41^2$ and $3321=41\times 81$, so $$n^2+n+41=41(41m^2+81m+41).$$ The first factor is 41. The second factor is at least 41 for every whole number $m$, because $41m^2+81m+41\ge 41$. Both factors therefore exceed 1, and the value is a product of two whole numbers greater than 1, which is what composite means. Distinct values of $m$ give distinct values of $n$, so the family is infinite. At $m=0$ the witness is $n=40$ and the value is $41\times 41=1681$. At $m=1$ the witness is $n=81$ and the value is $41\times 163=6683$, which agrees with $81^2+81+41=6561+81+41$. The lesson refines section 3.1 rather than contradicting it: one counterexample is enough to end a universal claim, and a universal claim can fail at infinitely many points, so the negation "there exists $n$" is satisfied by a single member while the set of witnesses may be as large as the whole numbers.

For (a), compute the two sides in order. At $n=2$, $2^2=4$ and $n^2=4$, so the strict inequality fails. At $n=3$, $8<9$. At $n=4$, $16=16$. At $n=5$, $32>25$. The smallest value at which the claim holds is 5.

For (b), assume $C(n)$ and $n\ge 3$. Then $$2^{n+1}=2\cdot 2^n>2n^2.$$ The step needs $2n^2\ge (n+1{)}^2=n^2+2n+1$, which rearranges to $n^2-2n-1\ge 0$. Completing the square gives $n^2-2n-1=(n-1{)}^2-2$, and at $n=3$ this is $4-2=2\ge 0$; the expression increases with $n$, so it stays positive for every $n\ge 3$. Therefore $2^{n+1}>(n+1{)}^2$, and the conditional holds for every $n\ge 3$.

Together the two answers locate the fault. The claim is false at $n=2,3$ and $4$, and the step is valid from $n=3$ onward. An induction with base case 2 would start from a false statement, and a valid step would then carry the falsehood upward: the step at $n=2$ also fails, since $2\cdot 4=8<9$. Moving the base case to 3 does not help either, because $C(3)$ is false. The induction becomes sound only when the base case sits where the claim first holds, at $n=5$, and then the step covers 5, 6, 7 and upward. Section 3.3 says the two obligations cover every case; here the pair of obligations covers nothing until the index is placed correctly, and the joint that fails is the index, which is the third shape catalogued in section 3.6.