Help with an arithmetic proof by induction

I didn't think to use the fact that ##b^{n - k} < b^n## for ##1 \leq k \leq n##. This simplifies the proof significantly.
  • #1
Entertainment Unit
16
1

Homework Statement


Show that if ##0 \leq a < b##, then
$$\frac {b^{n + 1} - a^{n + 1}} {b - a} < (n + 1)b^n$$

Homework Equations


None that I'm aware of.

The Attempt at a Solution


Proof (Induction)
1. Basis Case: Suppose ##n = 1##. It follows that:
$$\frac {b^{1 + 1} - a^{1 + 1}} {b - a} < (1 + 1)b^1$$
$$\frac {b^2 - a^2} {b - a} < 2b$$
$$b^2 - a^2< 2b(b - a)$$
$$b^2 - a^2< 2b^2- 2ab$$
$$-a^2< 2b^2$$

which is true for all ##0 \leq a < b##.

2. Inductive Step. Let ##k = n \geq 1## and suppose that:
$$\frac {b^{k + 1} - a^{k + 1}} {b - a} < (k + 1)b^k$$
This is where I can't make any progress. I can get the right-hand side to read ##(k + 2)b^{k + 1}## but doing so leaves the left-hand side of the inequality in a state that I can't get it to ##\frac {b^{k + 2} - a^{k + 2}} {b - a}##.
 
Physics news on Phys.org
  • #2
You don't need to use induction here.
The relevant equation you are missing is [tex]
b^{n+1} - a^{n+1} = (b-a)(b^n + ab^{n-1} + \dots + a^{n-1}b + a^n)
[/tex]
 
  • Like
Likes Entertainment Unit
  • #3
Thank you! I went down the path of proving it directly but struggled with that too.

Here's my completed proof:

Proof: Suppose

$$\frac {b^{n + 1} - a^{n + 1}} {b - a} < (n+1)b^n$$

It follows that
$$\frac {(b - a)(b^n + ab^{n - 1} + \dots + a^{n - 1}b + a^n)} {b - a} < (n+1)b^n$$
$$b^n + ab^{n - 1} + \dots + a^{n - 1}b + a^n < (n+1)b^n$$
$$b^n < (n+1)b^n$$

which is true for ##b \gt 0, n \geq 1##. Therefore,

$$\frac {b^{n + 1} - a^{n + 1}} {b - a} < (n+1)b^n\text{ ■}$$
 
Last edited:
  • #4
The proof is even easier: It follows from [itex]0 \leq a < b[/itex] that [itex]b^{n-k} a^{k} < b^n[/itex] for [itex]1 \leq k \leq n[/itex]. Hence
[tex]
\frac{b^{n+1} - a^{n+1}}{b-a} = \sum_{k=0}^n b^{n-k}a^k < \sum_{k=0}^n b^n = (n+1)b^n.
[/tex]
 
  • Like
Likes Entertainment Unit
  • #5
pasmith said:
The proof is even easier: It follows ...
Thanks for this!
 

FAQ: Help with an arithmetic proof by induction

What is a proof by induction?

A proof by induction is a mathematical technique used to prove that a statement holds for all natural numbers. It involves three steps: the base case, the inductive hypothesis, and the inductive step.

How do you know when to use proof by induction?

Proof by induction is typically used to prove statements about natural numbers, such as properties of sequences or series, divisibility, and inequalities. It is also commonly used in computer science to prove the correctness of algorithms.

What is the base case in a proof by induction?

The base case is the first value of the natural numbers that the statement is true for. It serves as the starting point for the proof and is usually the simplest case to prove.

What is the inductive hypothesis in a proof by induction?

The inductive hypothesis is the assumption that the statement is true for some natural number, usually denoted as k. This assumption is used to prove that the statement is also true for the next natural number, k+1.

What is the inductive step in a proof by induction?

The inductive step is the final step in a proof by induction. It involves using the inductive hypothesis to show that the statement is true for the next natural number after the base case. This step is repeated until the statement is proven to hold for all natural numbers.

Similar threads

Replies
9
Views
725
Replies
11
Views
834
Replies
9
Views
2K
Replies
11
Views
640
Replies
3
Views
1K
Replies
15
Views
1K
Replies
13
Views
2K
Back
Top