few problems on proving using induction

1) So I need to prove that

I did ;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,...

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 .

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

So let be the propositional function:

Then (Do you understand the notation I'm using here?)

is , which is true; is , which is also true. So is true .

(Do you understand this bit? It's a GP, first term 2, common ratio 2.)

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

Just start with:

Let be the statement (propositional function) involving : , and then use the formula for to show that . Then check that is true, and you're done.

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

Grandad