I am doing problems in Induction. What i know is:
First we need to test Base case, that is $P(n_0)$ should be verified.
Second we need to assume that $P(k)$ is True which is the inductive Hypothesis
Third we need to prove $P(k+1)$ is True using the above Hypothesis which gives the conclusion.
But the below problem made me to fall in a confusion.
When we assume $P(k)$ is True, does it mean all of $P(1),P(2),...P(k-1)$ are also True?
Here is the problem:
Prove using induction that $10^n-(5+\sqrt{17})^n-(5-\sqrt{17})^n$ is divisible by $2^{n+1}, \:\forall n \in N$
My try:
Obviously $P(1)$ is True.
I assumed that $P(k)$ is True: So we have:
$$10^{k}-(5+\sqrt{17})^{k}-(5-\sqrt{17})^{k}=2^{k+1} Q \to (1)$$ for some $Q \in N$
Now let $$P(k+1)=10^{k+1}-(5+\sqrt{17})^{k+1}-(5-\sqrt{17})^{k+1}$$ Using $(1)$ we get
$$\begin{array}{l} P(k+1)=10\left(10^{k}\right)-(5+\sqrt{17})^{k+1}-(5-\sqrt{17})^{k+1} \\ =10\left(2^{k+1} Q+(5+\sqrt{17})^{k}+(5-\sqrt{17})^{k}\right)-(5+\sqrt{17})^{k+1}-(5-\sqrt{17})^{k+1} \\ =5\left(2^{k+2}\right) Q+(5+\sqrt{17})^{k}(5-\sqrt{17})+(5-\sqrt{17})^{k}(5+\sqrt{17})\\ =5(2^{k+2})Q+(5+\sqrt{17})^{k-1}(8)+(5-\sqrt{17})^{k-1}(8)\\ =5(2^{k+2})Q+8P(k-1) \end{array}$$
Now according to my book, the author has taken $P(k-1)$ as True and proved the result. So my question is: When we assume $P(k)$ is True, does it mean all of $P(1),P(2),...P(k-1)$ are also True?
It is not true that $P(k)$ being true implies $P(i)$ is true for $i<k$. A usual induction proof does the following after the base case: $$P(k) \implies P(k+1)$$
But, the technique the author has used is often referred to as strong induction. It works according to the following: $$P(i) \space (\forall \space i \leqslant k) \implies P(k+1)$$ It can be used when you need more than just the previous case to solve a problem. The reason why it works is similar to the working of induction.
Essentially, you assume that all the previous cases are true, and use some (or all) of them to show that the next case is true. Now, the case you have proved becomes part of the list of initial cases you have proved and so on (similar to the domino effect of induction).