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$ Mar 10 '21 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
    Mar 10 '21 at 20:13
  • $\begingroup$ No, $s$ is indexed by the natural numbers, and that's what you induct on. $\endgroup$ Mar 10 '21 at 20:14
  • $\begingroup$ Okay i see, so how would i set up the RHS and LHS? $\endgroup$
    – Marcus F
    Mar 10 '21 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
    Mar 10 '21 at 20:21
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
    Mar 10 '21 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$ Mar 10 '21 at 20:17
  • $\begingroup$ do you know how i would set up LHS and RHS for bae case? $\endgroup$
    – Marcus F
    Mar 10 '21 at 20:27
  • $\begingroup$ See the edited answer. $\endgroup$ Mar 10 '21 at 20:32
  • $\begingroup$ wouldnt it be $LHS = 1 + 1 * k$ and $RHS = (1+k)^1$ $\endgroup$
    – Marcus F
    Mar 10 '21 at 20:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.