Question

Question #3ae9e

Answer 1

For a proof by induction we need a base case and a way to get from the base case to all other cases. For our base case, let's use `1` since it's the smallest natural number.

`2(1)+7 < (1+3)^2`

`2+7 < 4^2`

`9 < 16`

This is true. Now, let's assume that the statement `(2n+7)<(n+3)^2` is true for any natural number `n` and then prove that it must be true for `n+1` as well.

`(2(n+1)+7) < ((n+1)+3)^2`

`2n + 7 + 2 < ((n+3)+1)^2`

`2n + 7 + 2 < (n+3)^2 + 2(n+3) + 1`

`2n + 7 + 2 < (n+3)^2 + 2n + 6 + 1`

`2n + 7 + 2 < (n+3)^2 + 2n + 7`

`2 < (n+3)^2`

Which we know is true for any natural number, since `(n+3)` must be at least `4` and `4^2 = 16 > 2`.

So, we have proven that `2n+7 < (n+3)^2` for all `n in NN`.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Now, we need to prove the second statement. Again, let's use 1 as our base case:

`((1)+3)^2 le 2^((1)+3)`

`4^2 le 2^4`

`16 le 16`

This is true, since `16 = 16`. So, let's assume it's true for a number `n` and then find whether or not it is true for `n+1`.

`(n+3)^2 le 2^(n+3)`

`((n+1)+3)^2 le 2^((n+1)+3)`

`((n+3)+1)^2 le 2^((n+3)+1)`

`(n+3)^2 + 2(n+3) + 1 le 2 * 2^(n+3)`

`(n+3)^2 + (2n+7) le 2 * 2^(n+3)`

Now, here's where we use the first proof. We know that `(2n+7) le (n+3)^2`, and we're assuming that `(n+3)^2 le 2^(n+3)`. This means that `(2n+7) le 2^(n+3)` by the transitive property.

`-----------------------`
Also, remember this rule of inequalities (which makes sense intuitively if you think about it):

`if " " a le b " " and " " c le d`

`then " " (a+c) le (b+d)`

`-----------------------`

Therefore, since we know that:

`(n+3)^2 le 2^(n+3) " " and " " (2n+7) le 2^(n+3)`

We can confidently say that:

`(n+3^2) + (2n+7) le 2^(n+3) + 2^(n+3)`

`(n+3^2) + (2n+7) le 2*2^(n+3)`

And since we have proven this statement true, the previous statement `(n+3)^2 le 2^(n+3)` must also be true.

Final Answer