Prove by mathematical induction. \[ 4^{n} \geq 1+3 n \]

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