Let the property P(n) be the inequality.
\(1+3n\leq 4^n. \)
Establishing \(P(0) \), we see that \(1+3(0)=1 \) and \(4^0=1 \) hence \(P(0) \) is true.
Suppose, \(k\) is any integer with \(k\geq 0 \) such that
\( 1+3k\leq 4^k. \)
We must show
\(1+3(k+1)\leq 4^{k+1}.\)
By algebra, we see
\(1+3(k+1)=1+3k+3=(3k+1)+3\leq4^{k+1}=4^k\cdot4^1. \) - (1)
Since, \(1+3k \leq 4^k \) (by inductive hypothesis), we have
\((3k+1)+3\le 4^k+3\tag{2} \)
But, \((4^k+3\le 4^{k+1}=4\cdot 4^k=4^k+3\cdot 4^k)\iff (3\le 3\cdot 4^k), \forall k\ge 0\)
So that
\(4^k+3\le 4^{k+1}\tag{3} \)
Now combine (1),(2),(3) and you have that \( P(k)\implies P(k+1), \forall k\ge 0 \)
and you've already shown that \( P(0) \) is true, so our proof by induction is done.
2nd method:-
Let assume that
P(n) : \(4^n\geq\) 1 + 3n
Step - 1 :
For n = 1
P(1) : \(4^1\geq\) 1 + 3 \(\times \) 1
\(\Rightarrow\) P(1) : 4 = 4
\(\Rightarrow\) P(1) is true for n = 1
Step - 2 :
Let assume that P(n) is true for n = k, where k is some natural number.
P(k) : \(4^k\geq\) 1 + 3k ......(1)
Step - 3 :
Now,
We have to prove that P(n) is true for n = k + 1
: \(4^{k+1}\geq\) 1 + 3(k + 1)
Now, from equation (1),we have
\(4^k\geq\) 1 + 3k
On multiply by 4, on both sides we get
4 \(\times\) \(4^k\geq\) 4(1 + 3k)
\(4^{k+1}\geq\) 4 + 12k
can be rewritten as,
\(4^{k+1}\geq\) 1 + 3 + 3k + 9k > 1 + 3 + 3k
\(4^{k+1}\geq\) 1 + 3(1 + k)
\(\Rightarrow\) \(4^{k+1}\geq\) 1 + 3(1 + k)
\(\Rightarrow\) P(n) is true for n = k + 1
Hence,
By the Principle of Mathematical induction,
1 + 3n \(\leq\) \(4^n\). for all n \(\geq\) 1
