induction proof: (2n + 1)*a^n <= 1 + a + a^2 + ... + a^(2n)

[akramzine]

I stumbled across this induction problem that posted some solving difficulty

. . .Prove by induction for n a natural number:

. . . . .(2n + 1) × aⁿ < 1 + a + a² + ... + a²ⁿ

 

[akramzine]

I finally solved it:

. . .Let's suppose that (2n + 1) × aⁿ < 1 + a + a² + ... + a²ⁿ

. . .and show that (2(n +1) + 1) × aⁿ⁺¹ < 1 + a + a² + ... + a²⁽ⁿ⁺¹⁾

. . .which implies showing that (2(n +1) + 1) × aⁿ⁺¹ – 1 – a²⁽ⁿ⁺¹⁾ < a + a² + ... + a²ⁿ⁺¹

. . .We got (2n + 1) × aⁿ < 1 + a + a² + ... + a²ⁿ so [(2n + 1) × aⁿ] × a < (1 + a + a² + ... + a²ⁿ) × a

. . .so (2n + 1) × aⁿ⁺¹ < a + a² + a³ ... + a²ⁿ⁺¹

. . .We show that (2(n +1) + 1) × aⁿ⁺¹ – 1 – a²⁽ⁿ⁺¹⁾ < (2n + 1) × aⁿ⁺¹ < a + a² + a³ ... + a²ⁿ⁺¹

. . .(2(n +1) + 1) × aⁿ⁺¹ – 1 – a²⁽ⁿ⁺¹⁾ – (2n + 1) × aⁿ⁺¹ = –a²ⁿ⁺¹ + 2aⁿ⁺¹ – 1

. . .= –(aⁿ⁺¹ – 1)^2 < 0 so (2(n +1) + 1) × aⁿ⁺¹ – 1 – a²⁽ⁿ⁺¹⁾ < a + a² + a³ ... + a²ⁿ⁺¹

. . .Then (2(n +1) + 1) × aⁿ⁺¹ < 1 + a + a² + ... + a²⁽ⁿ⁺¹⁾

. . .Therefore: (2n + 1) × aⁿ < 1 + a + a² + ... + a²ⁿ

thank you for any intended help

 

[stapel]

I finally solved it:

. . .Let's suppose that (2n + 1) × aⁿ < 1 + a + a² + ... + a²ⁿ

. . .and show that (2(n +1) + 1) × aⁿ⁺¹ < 1 + a + a² + ... + a²⁽ⁿ⁺¹⁾

. . .which implies showing that (2(n +1) + 1) × aⁿ⁺¹ – 1 – a²⁽ⁿ⁺¹⁾ < a + a² + ... + a²ⁿ⁺¹

. . .We got (2n + 1) × aⁿ < 1 + a + a² + ... + a²ⁿ so [(2n + 1) × aⁿ] × a < (1 + a + a² + ... + a²ⁿ) × a

. . .so (2n + 1) × aⁿ⁺¹ < a + a² + a³ ... + a²ⁿ⁺¹

. . .We show that (2(n +1) + 1) × aⁿ⁺¹ – 1 – a²⁽ⁿ⁺¹⁾ < (2n + 1) × aⁿ⁺¹ < a + a² + a³ ... + a²ⁿ⁺¹

. . .(2(n +1) + 1) × aⁿ⁺¹ – 1 – a²⁽ⁿ⁺¹⁾ – (2n + 1) × aⁿ⁺¹ = –a²ⁿ⁺¹ + 2aⁿ⁺¹ – 1

. . .= –(aⁿ⁺¹ – 1)^2 < 0 so (2(n +1) + 1) × aⁿ⁺¹ – 1 – a²⁽ⁿ⁺¹⁾ < a + a² + a³ ... + a²ⁿ⁺¹

. . .Then (2(n +1) + 1) × aⁿ⁺¹ < 1 + a + a² + ... + a²⁽ⁿ⁺¹⁾

. . .Therefore: (2n + 1) × aⁿ < 1 + a + a² + ... + a²ⁿ

thank you for any intended help

You seem to have gone around in a circle, ending by "proving" what you'd initially "supposed" to be so. This is not a valid proof.

Instead, try using the induction-proof methodology (here):

1) Show that the proposed inequality is true for some natural number; say, for n = 1:

. . .Let n = 1. Then the left-hand side is:

. . . . .(2(1) + 1) × a¹ = (2 + 1)(a) = 3a

. . .And the right-hand side is:

. . . . .a⁰ + a¹ + a² + ... + a²⁽¹⁾ = a⁰ + a¹ + ... + a² = a⁰ + a¹ + a² = 1 + a + a²

. . .Is it true that 3a < 1 + a + a² ? Solve:

. . . . .3a < 1 + a + a²

. . . . .0 < a² – 2a + 1 = (a – 1)²

. . .Yes; for any value of a, the square on the right-hand side will be

. . .greater than or equal to zero. So the inequality holds for n = 1.

2) Then, do the assumption step; assume that the proposed inequality is true for some generic n = k:

. . .Let's assume that, for some generic n = k, that the inequality holds.

. . .That is, let's assume that (2k + 1) × a^k < 1 + a + a² + ... + a^2k

3) Then, let n = k + 1, and see if you can show the inequality still to be true.

. . .Now let's consider the next value, n = k + 1.

. . .On the left-hand side, we have:

. . . . .(2(k + 1) + 1) × a^k+1 = (2k + 2 + 1) × (a^k)(a) = [(2k + 1) + 2] × a(a^k)

. . .Rearranging a bit, we get:

. . . . .[(2k + 1) × a^k](a) + 2a^k+1

. . .By the induction assumption, we can substitute and get:

. . . . .[(2k + 1) × a^k](a) + 2a^k+1 < (a)[1 + a + a² + ... + a^2k] + 2a^k+1

. . . . .[(2k + 1) × a^k](a) + 2a^k+1 < a + a² + ... + a^2k + a^2k+1 + 2a^k+1

. . .Let's subtract the above from our desired result for the right-hand side.

. . . . .(1 + a + a² + ... + a^2k + a^2k+1 + a^2k+2) – (a + a² + ... + a^2k + a^2k+1 + 2a^k+1)

. . . . .= 1 + a^2k+2 – 2a^k+1 = 1 – 2a^k+1 + a^2(k+1) = ...

Where does this lead? What can you conclude?

Do the remaining two lines or so of the above, and you'll have a valid proof. :wink:

 

[akramzine]

thank you for your help i understand that my solution redaction wasn't beautifully correct