Prove by induction that $\;A^n = PD^nP^{-1}$

Question

Not sure how to prove the following statement.

$$A^n = PD^nP^{-1}$$

I started letting n = 1, so that is true. Then, I let n = 2 and 3. Again true. How should I finish the proof?

Any help is appreciated!

Here is the proof I got. Please make any corrections if needed.

Answer 1

Let $P(n)$ be a statement depending on a natural number $n$; in your example $P(n)$ is the statement $A^n=PD^nP^{-1}$. The principle of induction says that you can prove all the statements $P(n)$ (as $n$ varies), by first proving $P(1)$ (the base case), and then proving that if $P(k-1)$ is true for some $k\geq2$, then $P(k)$ is true (the induction step).

(Then, for example, if somebody asks you why $P(3)$ is true, you can say that $P(1)$ is true by the base case, so $P(2)$ must be true by the induction step, hence $P(3)$ is true by the induction step again.)

You claim you have proved $P(1)$, i.e. that $A=PDP^{-1}$, so you just have to prove the induction step, i.e. that if $A^{k-1}=PD^{k-1}P^{-1}$ then $A^k=PD^kP^{-1}$.

Update: to comment on attempted solution

Unfortunately your attempted solution contains several errors - it is probably easiest to comment line by line.

• Line 1: This isn't a proof of the base case, but an assertion that the base case is true. You need to actually say something about why it is true.

• Line 2: You haven't proved the induction step yet, so you can't conclude anything "by induction". (There is also nothing about $n=2$ that makes it particularly worth commenting on).

• Line 3: Again, you haven't proved the induction step yet. If this line was correct, you could stop here!

• Line 4: What you've written isn't exactly clear, but it looks like you're assuming the result again. You want to assume that $A^{k-1}=PD^{k-1}P^{-1}$ for a fixed $k$.

• Line 5: You aren't allowed to choose $k$; if you set $k=2$ when proving the induction step, you're not proving that $P(k-1)\implies P(k)$ for all $k$, which is what you want, but only that $P(1)\implies P(2)$. So how do you know that $P(3)$ is true?

I will try to summarise the principle again: to prove that $P(n)$ is true for all $n$, you should:

1. Prove that $P(1)$ is true; in your case, prove that $A=PDP^{-1}$.
2. Prove that if $k$ is any natural number with the property that $P(k-1)$ is true, then $P(k)$ is also true (written more concisely as "$P(k-1)\implies P(k)$ for all $k$"). In your case this means proving that if $A^{k-1}=PD^{k-1}P^{-1}$ (for some $k$ that you don't know, and are not allowed to choose) then $A^k=PD^kP^{-1}$.

Then you're done.

The reason this works is that once you have proved these things, then you have:

$$P(1)\implies P(2)\implies P(3)\implies\cdots\implies P(n)\implies\cdots$$

in which all of the implications hold by Point 2, and the left-most statement is true by Point 1, so in fact all of the statements are true.