# Further Maths - Induction for Divisibility

> Source: https://ollybritton.com/notes/a-level/further-maths/topics/induction-for-divisibility/ · Updated: 2021-01-05 · Tags: further-maths, induction

##### If you add a multiple of $4$ to something already divisible by $4$, what must be true about the answer??
It is also divisible by 4.

##### What is the two-step general technique used to show divisibility in induction??
* Assume $f(k)$ is divisible
* Show the difference between $f(k)$ and $f(k+1)$ is divisible.

##### How would you write the difference between $f(k)$ and $f(k+1)$??
$$
f(k+1) - f(k)
$$

##### If $$f(k + 1) - f(k) = 4\times 3^{2k}$$, what other statement could you write that shows clearly $f(k+1)$ is divisible by $4$??
$$
f(k+1) = f(k) + 4\times 3^{2k}
$$

##### How could you simplify $$3k^2 + 3k + 6$$??
$$
3k(k+1) + 6
$$

##### $$3k(k+1) + 6$$ You're trying to prove this statement is divisible by $6$. What new variable can you introduce??
$$
2m = k(k+1),\quad m \in \mathbb{Z}^{+}
$$

##### $$3k(k+1) + 6$$ Why can you substitute $2m = k(k+1)$??
Because the product of any two consecutive integers must be even.

##### Substitute $$2m = k(k+1)$$ into $$3k(k+1) + 6$$??
$$
6m + 6
$$

##### If $$f(k) = 2^{6k} + 3^{2k-2}$$, how could you rewrite $$63\times 2^{6k} + 8\times 3^{2k-2}$$ in terms of $f(k)$??
$$
63\times 2^{6k} + 63\times 3^{2k-2} - 55\times 3^{2k-2}
$$

$$
63\times(2^{6k} + 3^{2k-2}) - 55\times3^{2k-2}
$$

$$
63(f(k)) - 55\times3^{2k-2}
$$

##### If $$f(k) = 2^{6k} + 3^{2k-2}$$, what is the general technique (but not the process) to rewrite $$63\times 2^{6k} + 8\times 3^{2k-2}$$ in terms of $f(k)$??
Invent some extra terms that are cancelled out so it's in the form you want.

---
Olly Britton — https://ollybritton.com. Machine-readable index: https://ollybritton.com/llms.txt