# Inductive proof that $64 \mid 7^{2n} + 16n - 1$

Let us suppose that $$P(n)$$ be the statement –

$$P(n)$$: $$7^{2n} + 16n - 1$$ is divisible by $$64$$ or $$P(n)$$: $$64$$ | $$7^{2n} + 16n - 1$$

• Base Case:

We check if $$P(n)$$ holds true for $$n = 1$$. $$P(1):$$

$$7^{2.1} + 16.1 - 1= 64$$. As we know, $$64$$ divides $$64$$. Hence, $$P(1)$$ is true.

• Inductive Step:

Let us assume that $$P(n)$$ holds true for some arbitrary integer $$k$$ such that $$k > 0$$. In other words, we have $$P(k)$$ is true. Now, according to this step, we must prove that $$P(k+1)$$ holds true as well.

We have $$P(k)$$ is true, or $$64$$ | $$7^{2k} + 16k - 1$$

Hence, we can infer that $$7^{2k} + 16k - 1$$ is a factor of $$64$$ and write that $$7^{2k} + 16k - 1 = 64m$$ where $$m$$ is some integer such that $$m > 0$$

And we have to show that $$64$$ | $$7^{2(k+1)} + 16(k+1) - 1$$

• Proof:

We have $$P(k+1)$$

= $$7^{2(k+1)} + 16(k+1) - 1$$

=$$49.7^{2k} + 16(k+1) - 1$$

Since k is an integer, so in $$16k - 1$$ and so is $$49(16k - 1)$$. Hence, adding and subtracting $$49(16k - 1)$$, we have

P(k + 1) = $$49.7^{2k} + 16(k+1) - 1 + 49(16k - 1) - 49(16k - 1)$$

= $$49.7^{2k} + 16(k+1) - 1 + 49.16k - 49 - 49.16k + 49$$

= $$49(7^{2k} + 16k - 1) + 16.48k + 64$$

= $$49.64m + 12.64k + 64$$

= $$64(49m + 12k + 1)$$

= $$64p$$ where p is some integer equal to $$49m + 12k + 1$$. This is because, since m and k are integers, so is $$49m + 12k + 1$$.

Hence, we have proved that that $$P(k + 1)$$ is a factor of 64 or in other words, $$64$$ divides $$7^{2(k+1)} + 16(k+1) - 1$$.

So by the step of Inductive hypothesis, we have showed that if $$P(n)$$ holds true for some arbitrary integer $$k$$, it holds true for $$k+1$$ as well. This completes our proof by Induction.

Is this correct?

• There are som $n$'s which should be $k$'s after your "We have $P(k)$ is true". Also, replace your title by a shorter but more informative one, like "Inductive proof that $64\mid7^{2n}+16n-1$". And don't write "$P(1)=$ some number" ($P(1)$ is an assertion, not a number). Commented Nov 22, 2022 at 21:42
• Can you elaborate on what you mean by “research proof?” Commented Nov 22, 2022 at 22:30
• @templatetypedef noting much, just a short assignment for one of my classes Commented Nov 23, 2022 at 0:18
• @AnneBauval appreciate it thanks Commented Nov 23, 2022 at 0:18
• Don't say $P(k+1) = ......$. $P(k+1)$ is a statement about $k+1$. If you want a number to serve as notation for $7^{2k} + 16k -1$, introduce one. Say let $A(n) = 7^{2n} + 16n -1$. THe your $P(k)$ statement is $P(k) =$" $A(n)$ is divisible by $64$.... Otherwise....Eyeballing your proof looks correct and how I'd do it. But I didn't actually check that your arithmetic actually works though. If it does you proof is valid. Commented Nov 23, 2022 at 1:56

Much of your work can be simplified by defining $$f(n) = 7^{2n} + 16n - 1$$ and then noting that if the statement $$64 \mid f(k)$$ is true, then $$f(k+1) - 49 f(k) = 16(k+1) - 1 - 49(16k - 1) = -64(12k-1);$$ that is to say, $$f(k+1) = 49f(k) - 64(12k-1),$$ so $$64 \mid f(k+1)$$ and by the induction hypothesis, $$f(n)$$ is divisible by $$64$$ for all positive integers $$n$$.