# few problems on proving using induction

• Mar 21st 2009, 09:10 PM
meg0529
few problems on proving using induction
1) So I need to prove that $(1+x)^n <= 1 + xn (x>= -1)$

I did $(1+x)^n+1 >= 1+x(n+1)$ ;then I just don't know where to go.
Then There are 2 sequence ones that I don't even know where to begin

a) Let Fn be the n-th term of the Fibonacci Sequence 1, 1, 2, 3, 5, 8,.. Defined by the rule:
F(n+2) = F(n) + F(n+1) [ Fn is F sub n]
prove by induction that F1+F2 +....+Fn $<=$2^(n+1)

b) The sequence a1, a2, a3, a4, ... an,... [again a sub n]
of positive integers defined by the rule:
a1 =1 a(n+1) = 3an (3 times a sub n) ( n = 1, 2,3,..) Prove that an = 3 ^(n-1) for n= 1,2,...
• Mar 22nd 2009, 12:50 AM
Induction
Hello meg0529
Quote:

Originally Posted by meg0529
1) So I need to prove that $(1+x)^n \color{red}<=\color{black} 1 + xn (x>= -1)$

I did $(1+x)^n+1 >= 1+x(n+1)$ ;then I just don't know where to go.

You mean $(1+x)^n >= 1 + xn (x>= -1)$, of course.

So let $P(n)$ be the propositional function $(1+x)^n >= 1 + xn (x>= -1)$

Then, provided $(1+x) \ge 0$, we can multiply both sides by $(1+x)$. So for $x\ge -1$:

$P(n) \Rightarrow (1+x)^{n+1} \ge (1+x)(1+nx)$

$\Rightarrow (1+x)^{n+1} \ge 1 + (n+1)x + nx^2$

$\Rightarrow (1+x)^{n+1} \ge 1 + (n+1)x$, since $n>0 \Rightarrow nx^2 \ge 0$

$\Rightarrow P(n+1)$

Can you complete it now?

(I must sign off now - I'll look at the others later, if no-one else does first.)

• Mar 22nd 2009, 08:56 AM
Induction on a Fibonacci sequence
Hello again meg0529
Quote:

Originally Posted by meg0529
a) Let Fn be the n-th term of the Fibonacci Sequence 1, 1, 2, 3, 5, 8,.. Defined by the rule:
F(n+2) = F(n) + F(n+1) [ Fn is F sub n]
prove by induction that F1+F2 +....+Fn $<=$2^(n+1)

In fact, we can prove the strict inequality $\sum_{i=1}^nF_i < 2^{n+1}$.

This is a little bit different from the usual induction proof. Notice that when we add the next term, $F_{n+1}$, we would need to prove that the new sum < $2^{n+2}= 2^{n+1} + 2^{n+1}$. So if we can prove that $F_{n+1} < 2^{n+1}$, we're there. We do this in, again, a slightly unusual way, by assuming that we have two consecutive values of $n$ for which it's true.

So let $P(n)$ be the propositional function: $F_n < 2^n$

Then $(P(n) \wedge P(n-1)) \Rightarrow F_n + F_{n-1}< 2^n+2^{n-1} = 2^n(1 + \tfrac{1}{2})$ (Do you understand the notation I'm using here?)

$\Rightarrow F_{n+1} < 2^{n+1}$

$P(1)$ is $F_1 < 2^1$, which is true; $P(2)$ is $F_2 < 2^2$, which is also true. So $P(n)$ is true $\forall n \ge 1$.

$\Rightarrow \sum_{i=1}^nF_i < \sum_{i=1}^n2^i = \frac{2(2^n-1)}{2-1} =2^{n+1} - 2$ (Do you understand this bit? It's a GP, first term 2, common ratio 2.)

$\Rightarrow \sum_{i=1}^nF_i < 2^{n+1}$

Quote:

b) The sequence a1, a2, a3, a4, ... an,... [again a sub n]
of positive integers defined by the rule:
a1 =1 a(n+1) = 3an (3 times a sub n) ( n = 1, 2,3,..) Prove that an = 3 ^(n-1) for n= 1,2,...
Have you tried this question? If you can't to it, then you're really not understanding anything about induction at all. The $a_n$ here are simply the terms of a GP.

Let $P(n)$ be the statement (propositional function) involving $n$: $a_n = 3^{n-1}$, and then use the formula for $a_{n+1}$ to show that $P(n) \Rightarrow P(n+1)$. Then check that $P(1)$ is true, and you're done.

Show us your attempt if you'd like us to check it for you.

• Mar 22nd 2009, 11:53 AM
meg0529
Thanks a lot Grandpa, I'll work them out and see how it goes. My professor has done a real bad job of explaining induction and I'm working off of the worst textbook ever, so I'm quite shakey on this stuff. I'll work em out and post what what I get.
• Mar 22nd 2009, 12:38 PM
meg0529
$\Rightarrow (1+x)^{n+1} \ge 1 + (n+1)x$, since $n>0 \Rightarrow nx^2 \ge 0$

I don't fully understand why we can drop the nx^2...
• Mar 22nd 2009, 12:45 PM
Hello meg0529
Quote:

Originally Posted by meg0529
$\Rightarrow (1+x)^{n+1} \ge 1 + (n+1)x$, since $n>0 \Rightarrow nx^2 \ge 0$

I don't fully understand why we can drop the nx^2...

$x^2 \ge 0$ for all values of $x$. So if $n > 0$, $nx^2 \ge 0$. Therefore $1+(n+1)x + nx^2 \ge 1+(n+1)x$.

OK?

• Mar 22nd 2009, 01:10 PM
meg0529
I see the inequality, I just don't know how to interpret it. If 1 + x(n+1)+nx^2 was less than 1+x(n+1), we wouldn't need to worry for as long as we can prove that (1+x)^(n+1) is >= 1+x(n+1). but in this case 1 + x(n+1)+nx^2 is larger than 1+x(n+1) (Headbang)
• Mar 22nd 2009, 02:25 PM
Hello meg0529
Quote:

Originally Posted by meg0529
I see the inequality, I just don't know how to interpret it. If 1 + x(n+1)+nx^2

Quote:

Originally Posted by meg0529
was less than 1+x(n+1)???, we wouldn't need to worry for as long as we can prove that (1+x)^(n+1) is >= 1+x(n+1). but in this case 1 + x(n+1)+nx^2 is larger than 1+x(n+1) (Headbang)

What's the problem here? We have $A \ge B$ and $B \ge C$. So surely $A \ge C$. I repeat: what's the problem?