# few problems on proving using induction

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

I did $\displaystyle (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 $\displaystyle <=$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 21st 2009, 11:50 PM
Induction
Hello meg0529
Quote:

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

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

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

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

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

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

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

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

$\displaystyle \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, 07: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 $\displaystyle <=$2^(n+1)

In fact, we can prove the strict inequality $\displaystyle \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, $\displaystyle F_{n+1}$, we would need to prove that the new sum < $\displaystyle 2^{n+2}= 2^{n+1} + 2^{n+1}$. So if we can prove that $\displaystyle 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 $\displaystyle n$ for which it's true.

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

Then $\displaystyle (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?)

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

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

$\displaystyle \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.)

$\displaystyle \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 $\displaystyle a_n$ here are simply the terms of a GP.

Let $\displaystyle P(n)$ be the statement (propositional function) involving $\displaystyle n$: $\displaystyle a_n = 3^{n-1}$, and then use the formula for $\displaystyle a_{n+1}$ to show that $\displaystyle P(n) \Rightarrow P(n+1)$. Then check that $\displaystyle 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, 10: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, 11:38 AM
meg0529
$\displaystyle \Rightarrow (1+x)^{n+1} \ge 1 + (n+1)x$, since $\displaystyle n>0 \Rightarrow nx^2 \ge 0$

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

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

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

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

OK?

• Mar 22nd 2009, 12: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, 01: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 $\displaystyle A \ge B$ and $\displaystyle B \ge C$. So surely $\displaystyle A \ge C$. I repeat: what's the problem?