0
$\begingroup$

For all $s ∈ N$ and all $k > 0$ it holds that $1+sk ≤(1+k)^s$

How would one use induction to prove this statement?

Im following the basic steps: First do base case then do induction step but i dont know how to even set the base case up correctly. Im setting up RHS and LHS to prove base case, but im not sure how to do it when there is multiple variables.

$\endgroup$
5
  • $\begingroup$ Hint: induction as we know it is on countable sets. Firsr set $s = 1$ to see what happens, then assume the statement holds for $s = m$, then try to prove for $m+1$. $\endgroup$ Commented Mar 10, 2021 at 20:10
  • $\begingroup$ ah okay so i should just worry about the "s" variable because its for that we are proving? $\endgroup$
    – Marcus F
    Commented Mar 10, 2021 at 20:13
  • $\begingroup$ No, $s$ is indexed by the natural numbers, and that's what you induct on. $\endgroup$ Commented Mar 10, 2021 at 20:14
  • $\begingroup$ Okay i see, so how would i set up the RHS and LHS? $\endgroup$
    – Marcus F
    Commented Mar 10, 2021 at 20:14
  • $\begingroup$ should i just replace both s and k with 1 for base case? in both LHS and RHS? $\endgroup$
    – Marcus F
    Commented Mar 10, 2021 at 20:21

1 Answer 1

0
$\begingroup$

For $s=1$, LHS$=1+k$, and RHS$=(1+k)$. Therefore the statement is true. Assume that it is true for $s=s'$. Then

$$ (1+k)^{s'+1} = (1+k)(1+k)^{s'} \geq (1+s'k)(1+k) = 1+k+s'k+s'k^2 \geq 1+(1+s')k. $$

In the last inequality use the fact that $k>0$.

$\endgroup$
8
  • $\begingroup$ 0 is not part of natural numbers no? So i have to prove it for 1 base case, and im required to set up LHS and RHS i believe $\endgroup$
    – Marcus F
    Commented Mar 10, 2021 at 20:16
  • $\begingroup$ You are right it is in general not considered as a part of the natural number. But your inequality is true for all non-negative integers! The base case $s=1$ is also trivial. Check! $\endgroup$ Commented Mar 10, 2021 at 20:17
  • $\begingroup$ do you know how i would set up LHS and RHS for bae case? $\endgroup$
    – Marcus F
    Commented Mar 10, 2021 at 20:27
  • $\begingroup$ See the edited answer. $\endgroup$ Commented Mar 10, 2021 at 20:32
  • $\begingroup$ wouldnt it be $LHS = 1 + 1 * k$ and $RHS = (1+k)^1$ $\endgroup$
    – Marcus F
    Commented Mar 10, 2021 at 20:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .