Thread: Stuck on Simple Inductive Proof

1. Stuck on Simple Inductive Proof

Show that for all $n \geq 0,$
$3^{2n}+4^{n+1}$ is a mulitple of 5 using an inductive proof.

I think that I have started this right but I am not sure if it is complete or correct.

$1) \ p(0) = 3^{3(0)}+4^{(0)+1}=1+4=5$
$2) \ Assume \ p(n)= 3^{2n}+4^{n+1} \ is \ multiple \ of \ 5,$
$p(n+1) = p(n)+3^{2(n+1)}+4^{(n+1)+1}$
$= 3^{2n}+4^{n+1}+3^{2n+2}+4^{n+2}$
$= 3^{2n}+4^{n+1}+3^{2n}(9)+4^{n+1}(4)$
$= 3^{2n}(1+9)+4^{n+1}(1+4) \ by \ factoring$
$= 3^{2n}(10)+4^{n+1}(5)$

So it appears to me that both terms are indeed multiples of 5; however, I thought the original p(n) would be factored out of the equation. In truth, it just looks a little funny. A little help or clarification would be greatly appreciated.

Show that for all $n \geq 0,$
$3^{2n}+4^{n+1}$ is a mulitple of 5 using an inductive proof.

I think that I have started this right but I am not sure if it is complete or correct.

$1) \ p(0) = 3^{3(0)}+4^{(0)+1}=1+4=5$
$2) \ Assume \ p(n)= 3^{2n}+4^{n+1} \ is \ multiple \ of \ 5,$
$p(n+1) = p(n)+3^{2(n+1)}+4^{(n+1)+1}$
$= 3^{2n}+4^{n+1}+3^{2n+2}+4^{n+2}$
$= 3^{2n}+4^{n+1}+3^{2n}(9)+4^{n+1}(4)$
$= 3^{2n}(1+9)+4^{n+1}(1+4) \ by \ factoring$
$= 3^{2n}(10)+4^{n+1}(5)$

So it appears to me that both terms are indeed multiples of 5; however, I thought the original p(n) would be factored out of the equation. In truth, it just looks a little funny. A little help or clarification would be greatly appreciated.
Your proof is incorrect - you used the wrong value for $P(n+1)$. Note that $P(n+1)$ is sustained simply by "switching" every n you had in the original expression with n+1. Your proof should have been as follows (skipping the base case):

If $P(n) = 3^{2n}+4^{n+1}$ then $P(n+1) = 3^{2(n+1)} + 4^{(n+1+1)} = 9\cdot 3^{2n} + 4\cdot 4^{n+1} =$ $4(3^{2n} + 4^{n+1}) + 5 \cdot 3^{2n} \overbrace{=}^{P(n)} 5k + 5\cdot 3^{2n} = 5(k+3^{2n})$ for some $k \in \mathbb{N}$

3. Originally Posted by Defunkt
$4(3^{2n} + 4^{n+1}) + 5 \cdot 3^{2n} \overbrace{=}^{P(n)} 5k + 5\cdot 3^{2n} = 5(k+3^{2n})$ for some $k \in \mathbb{N}$
Thank you for your quick response. I am following well up until here. What just happened? I don't think I'm familiar with this notation.

4. The notation meant to illustrate that I used the induction assumption that P(n) is true to get that equality:

$P(n+1): 3^{2(n+1)} + 4^{(n+1+1)} = 9\cdot 3^{2n} + 4\cdot 4^{n+1} =$ $4(3^{2n} + 4^{n+1}) + 5 \cdot 3^{2n}$

But since you assumed $P(n): 3^{2n}+4^{n+1} = 5k, \ k \in \mathbb{N}$, you get:

$P(n+1): 4(3^{2n} + 4^{n+1}) + 5 \cdot 3^{2n} = 4 \cdot 5k + 5 \cdot 3^{2n}$ $= 5(k+3^{2n})$, which is clearly a multiple of 5. And so P(n+1) is true.

5. I have several suggestions for making inductive proofs. I don't have the weight of education research methodology behind them, so maybe there are more efficient ways of learning induction. However, these recommendations are easy to follow, and they will keep you from 90% of errors, according to my experience.

1. Distinguish between propositions and numbers. Proposition is a statement that can be either true or false. E.g., "It is raining", "Every even number is divisible by four", "2 + 2 = 5 implies 3 * 0 = 100" (the second is false; the rest are true).

You cannot add propositions using regular numeric addition. The expression True + False is meaningless. On the other hand, numbers cannot be true or false. Thus, $\sum_{i=0}^n i^2$ is not a proposition; it's a number.

2. Know what a property (or predicate, or relation) is. A property is just like proposition, but it requires a number as input. E.g., $x=0$ can be either true or false depending on $x$; by itself it is not a proposition. If we denote $P(x)$ to be $x = 0$, then the proposition $P(0)$ is true and $P(1)$ is false. To remind, $P(0) + P(1)$ is meaningless.

Notation: I will write $P\Leftrightarrow Q$ to mean that $P$ and $Q$ are equivalent propositions (both are true or both are false). I prefer using = for numbers and $\Leftrightarrow$ for propositions in order to stress the difference. Also, I will write $n\mathrel{\vdots} 5$ to mean that $n$ is a multiple of 5.

3. Start the proof by identifying the number property that you need to establish for every natural number. This is usually very easy to do because most statements to prove have the form "For all natural $n$, $P(n)$" for some property $P$. So the first thing is to write what $P(n)$ is. E.g., in your case the proposition to prove is "For all natural $n$, $(3^{2n}+4^{n+1})\mathrel{\vdots}5$"; therefore,

$P(n)\Leftrightarrow(3^{2n}+4^{n+1})\mathrel{\vdots }5$

Make sure to write the general form of $P$: not $P(0)$ or $P(5)$, but $P(n)$ for a variable $n$. Also, make sure that $P(n)$ (when $n$ is unbound) is not a proposition; it is a property that becomes a proposition when $n$ is given. Equally important, $P(n)$ is not a number. Thus, writing $P(n) = 3^{2n}+4^{n+1}$ is incorrect.

4. After this, it's easy. Write and prove the base case $P(0)$ -- a proposition.

Base case $P(0)$: $3^{2\cdot0}+4^{0+1}\mathrel{\vdots}5$

5. The induction step consists of proving the following proposition: For all $n$, $P(n)$ implies $P(n+1)$. To prove this, fix an arbitrary $n$ and write the assumption, or induction hypothesis (IH), $P(n)$. In this case,

IH: Assume $P(n)$, i.e., $3^{2n}+4^{n+1}\mathrel{\vdots}5$

Next write what we need to prove: $P(n+1)$. In this case it is:

Need to prove $P(n+1)$: $3^{2(n+1)}+4^{(n+1)+1}\mathrel{\vdots}5$

(At the risk of being annoying, I remind that $P(n)$ and $P(n+1)$ are not numbers. Now that we fixed some concrete $n$, they became propositions.)

The proof was given in the post above. Instead of $P(n)=4(3^{2n}+4^{n+1})+5\cdot 3^{2n}\overbrace{=}^{P(n)} 5k+5\cdot 3^{2n}$ one should write

By IH, $3^{2n}+4^{n+1}=5k$ for some natural number $k$; therefore
$3^{2(n+1)}+4^{(n+1)+1}=4(3^{2n}+4^{n+1})+5\cdot 3^{2n}=4\cdot 5k+5\cdot 3^{2n}$, which is a multiple of 5.

(Note that I did not write $P(n)$ or $P(n+1)$ in the last two lines because they consists of a chain of equalities of numbers.)

I hope this helps.

Evgeny

6. Thanks

Thank you for all the help. I understand it completely. Also, thank you for all of the clarifications. It shed a lot of light on several of my recent doubts.

For others watching this thread I thought it might by helpful to make this step a little more explicit as it confused me a little at first.

$(9)3^{2n}+(4)^{4n+1}$

The coefficient is broken up in order to factor out $3^{2n}+4^{4n+1}$.

$(5)3^{2n}+(4)3^{2n}+(4)4^{4n+1}$ This is like $9A=5A+4A$.

$4(3^{2n}+4^{4n+1})+5(3^{2n})$