1

I have a general question regarding induction, with an example provided. I'd also like any critique in my proof.

Suppose I'm trying to prove the following.

Define a sequence of integers a0, a1, a2, ... as follows:

$a_i$ = 2 if 0 $\le$ i $\le$ 2

$a_i$ = $a_{i-1}$ + $a_{i-2}$ + $a_{i-3}$ for i > 2

Prove that $a_n$ < $2^n$ for every integer n $\ge$ $2.$

I approach the proof as follows, using complete induction.

Base case:

1) Let i = 2, then $a_2$ = 2, and $2$ $\lt$ $2^2$ is true.

2) Let i = 3, then

$a_3$ = $a_{3-1}$ + $a_{3-2}$ + $a_{3-3}$

= 2 + 2 + 2

= 6 $\lt$ $2^3$ is true.

Induction Hypothesis: Suppose P(j) holds such that 2 $\le$ j < k. We need to show that p(k) holds, ie, $a_k$ $\lt$ $2^k$.

Induction Step:

$a_k$ = $a_{k-1}$ + $a_{k-2}$ + $a_{k-3}$

$\lt$ $2^{k-1}$ + $2^{k-2}$ + $2^{k-3}$ [By our induction hypothesis, k - 1, k - 2, and k-3 are all less than k and hold by IH.]

$\lt$ $2^k ({2^{-1} + 2^{-2} + 2^{-3}})$ [Algebra]

$\lt$ $2^k$(${7/8}$)

$\lt$ $2^k(7/8)$ $\lt$ $2^k$ [This to me is trivially true, and where I would like critique on. Is there a better way of showing this is true?]

We have that $a_k$ < $2^k$, which is what we wanted to show.

Generally with my induction proofs I always get the inequality in some form such that it is evident to see that it is less than what we want to show or "substitute" into the inequality (ie: if a > b and b > c then a > c). Sometimes this involves a smaller remark on the side that I attempt to build an inequality to show this is true).

How can I show these sorts of steps better? It's even more tricky with polynomials and such.

TimelordViktorious
  • 862
  • Is using induction mandatory? – Soham Sep 25 '16 at 17:32
  • Yep. They are exercises in complete induction. – TimelordViktorious Sep 25 '16 at 17:47
  • You have to be allowed some axioms and definitions. $2^k(7/8) < 2^k$ because $7/8 < 1$ and $2^k > 0$ so $2^k(7/8) < 2^k*1 = 2^k$. That's it. $a > b$ and $b > c$ then $a > c$ because order is transitive. That's it. – fleablood Sep 25 '16 at 18:07
  • Your proof is fine and you've shown everything that it can be reasonably expected for you to show. – fleablood Sep 25 '16 at 18:10
  • you're proof looks fine, what may be annoying you is that an upper bound of 2^n isn't a particularly spectacular result about the sequence – JMP Sep 25 '16 at 19:02

1 Answers1

0

It seems to me you are worried about three things.

1) If $a' < a$ and $b' < b$ and $c' < c$ can we say $a' + b' + c' < a + b + c$

The answer is yes. If $x < y$ then $x + a < y + a$ is a basic axiom of order so

$a' < a \implies a' + b' < a + b'$

$b' < b \implies a + b' < a + b$

And $c' < c \implies a' + b' + c' < a + b' + c' < a + b + c' < a + b + c$.

which brings up issue two

2) If $a < b$ and $b < c$ can we say $a < c$.

The answer is yes. Order is defined/axiomatically assumed to be transitive. This is a given-- for this exercise or in any context where order is presumed.

3) if $a < b$ then is $xa < xb$ (e.g. if $7/8 < 1$ so is $2^k(7/8) < 2^k *1$?)

The answer is CONDITIONALLY yes. If $x> 0$ and $a<b$ then $xa < xb$. This is a given axiom of ordered fields (or which the real numbers are one). This is a given.

If, however $x = 0$ then $0a = 0 = 0b$ of course and if $x < 0$ then $(-x)a < (-x)b$ so $(-x) a + (x)b < 0$ (see 1) and $xb < xa$. So if $x < 0$ then $xb < xa$. This is a basic proposition (not an axiom but easily proven). For this exercise you can take it as a given.

====

In some classes you will be given a formal and abstract definition of "<" and a formal and abstract definition of an "ordered field" of with the real numbers are one example and given some basic definitions and axioms and you will be asked to prove very basic propositions. (For example that if $x<y$ then $-y < -x$ or $1/y < 1/x$ or that $x^2 \ge 0$ and so on.)

But for now, we can simply take these all as given.

fleablood
  • 124,253