Can someone post a solution to this question along with an explanation please? I got a test tomorrow and im having trouble understanding this.
Prove by induction:
4^n+1 + 5^n-1 is divisible by 21 ∀ n ∈ N,n>=1
I'm guessing you mean
$4^{n+1}+5^{n-1}$ is divisible by $21, ~~\forall n \in \mathbb{N}, n\geq 1$
But maybe not since
$n=1 \Rightarrow 4^2+1=17 \neq 21k$
$n=2 \Rightarrow 4^3+5 = 69 \neq 21k$
I show that in general your statement is incorrect.
Could you repost the correct statement you're trying to prove?
Romsek has given TWO examples showing that what you are trying to prove is false.
In particular, he has shown that your base case is false. Let's go over it again.
$n = 1 \implies 4^{(n + 1)} = 4^2 = 16\ and \ 5^{(n - 1)} = 5^0 = 1 \implies$
$4^{(n + 1)} + 5^{(n - 1)} = 16 + 1 = 17,$ which is clearly not divisible by 21.
Perhaps if you showed how you "proved" it true if n = 1, we could figure out what the problem actually is.
Okay so the "inductive hypothesis" is that $\displaystyle 4^{k+1}+ 5^{2k-1}= 21m$ for some integer m.
Then $\displaystyle 4^{(k+1)+ 1}+ 5^{2(k+1)- 1}= 4(4^{k+1})+ 25(5^{2k-1})= 4(4^{k+1}+ 5^{2k-1})+ 21(5^{2k-1})$
Can you finish from here?
I am going to give you this one so you see the logic of a proof by induction. As for finding a proof of any kind, there is no rule book: it takes creativity.
$H\ is\ the\ set\ such\ that\ n \in H \implies n \in\ \mathbb N,\ n \ge 1,\ and\ \dfrac{4^{n + 1} + 5^{2n - 1}}{21} \in \mathbb N.$ But H may be the empty set.
$1 \in \mathbb N,\ and\ 1 \ge 1,\ and\ \dfrac{4^{1 + 1} + 5^{2 * 1 - 1}}{21} = \dfrac{4^2 + 5^1}{21} = \dfrac{16 + 5}{21} = \dfrac{21}{21} = 1 \in \mathbb N.$
This is just arithmetic and you got it but it implies something very important, namely:
$\therefore 1 \in H.$ You have proved that H is not empty.
Now we choose an arbitrary member of H and call it k. This is called an inductive hypothesis for reasons that elude me because we have proved that at least one such number exists.
$Let\ k\ be\ an\ arbitrary\ member\ of\ H \implies k \in\ \mathbb N,\ k \ge 1,\ and\ \dfrac{4^{k + 1} + 5^{2k - 1}}{21} \in \mathbb N.$
$Let\ m = \dfrac{4^{k + 1} + 5^{2k - 1}}{21} \implies m \in \mathbb N\ and\ 4^{k + 1} + 5^{2k - 1} = 21m.$ With me to here?
Now we want to prove that k + 1 is also a member of H. It's trivially obvious that k + 1 is a natural number greater than or equal to 1 because those things are true of k. So the trick is to prove that the third condition for membership in H is met by k + 1. Very generally, you do that by finding out a way to reduce that third condition for k + 1 into something related to that same condition for k. This may require virtually no creativity or a lot of it. It is what makes proofs an art. Halls of Ivy came up with this bit of creativity starting from setting up the relevant expression for k + 1.
$\dfrac{4^{(k + 1) + 1} + 5^{2(k + 1) - 1}}{21} = \dfrac{4^{k + 2} + 5^{2k + 1}}{21} = \dfrac{4\left(4^{k + 1}\right) + 25\left(5^{2k - 1}\right)}{21} = \dfrac{4\left(4^{k + 1}\right) + 4\left(5^{2k - 1}\right) + 21\left(5^{2k - 1}\right)}{21} = $
$\dfrac{4\left(4^{k + 1} + 5^{2k - 1}\right) + 21\left(5^{2k - 1}\right)}{21} = \dfrac{4\left(21m\right) + 21\left(5^{2k - 1}\right)}{21} = \dfrac{21\left(4m + 5^{2k - 1}\right)}{21} = 4m + 5^{2k - 1}.$
$But\ 4m\ and\ 5^{2k - 1} \in \mathbb N \implies 4m + 5^{2k - 1} \in \mathbb N \implies \dfrac{4^{(k + 1) + 1} + 5^{2(k + 1) - 1}}{21} \in \mathbb N.$
So the third condition is met for k + 1.
$\therefore k + 1 \in H.$
$THUS, H = \mathbb N.$