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,...

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.

Just start with:

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.

Grandad