Determine closed expression for b(n) without recursion or product

[maxmilian]

determine a closed expression for b(n), given
b(0) = 3
b(n+1) = 2+\prod (k=0 to n) * b(k) , n >= 0 , without using recursion og or the product given by \prod.


I want to start out by b(n+1) -1 = (b(n)-1)^2 for n >= 0 , but I am not sure.

kind regards
Maxmilian

 

[Ray Vickson]

determine a closed expression for b(n), given
b(0) = 3
b(n+1) = 2+\prod (k=0 to n) * b(k) , n >= 0 , without using recursion og or the product given by \prod.


I want to start out by b(n+1) -1 = (b(n)-1)^2 for n >= 0 , but I am not sure.

kind regards
Maxmilian

What does the word "wanna" mean?

Have you tried writing out the first few b(k), to see if there is any discernible pattern?

RGV

 

[maxmilian]

oh sry, want to is my street slang for "want to".
And no I havent

 

[Curious3141]

The usual way to tackle this sort of problem is to write out the first few terms of the sequence, discern the pattern, then prove it by induction.

Hint: think in terms of powers of 2 plus a little something.

 

[maxmilian]

The usual way to tackle this sort of problem is to write out the first few terms of the sequence, discern the pattern, then prove it by induction.

Hint: think in terms of powers of 2 plus a little something.

Thx for your reply.
so for n = 1 , I am getting ;

2 + b(0) *b(1) = 2 + 3 * b(1)

for n = 2 ;

2 + 3 * b(1) * b(2)

edit: could 2+3*b(n)! be a solution to the pattern ?

Can anyone give me a hint for what I should do next ?

 

[maxmilian]

any help is still appreciated

 

[Curious3141]

Thx for your reply.
so for n = 1 , I am getting ;

2 + b(0) *b(1) = 2 + 3 * b(1)

for n = 2 ;

2 + 3 * b(1) * b(2)

edit: could 2+3*b(n)! be a solution to the pattern ?

Can anyone give me a hint for what I should do next ?

No.

b(n+1) = 2 + ∏(k from 0 to n) b(k)

So b(1) = 2 + ∏(k from 0 to 0)b(k) = 2 + b(0) = 2 + 3 = 5.

Can you now work out b(2), b(3), b(4) and b(5)? Try and see the pattern, then I (or someone else) can guide you through the induction if you still have problems.

 

[maxmilian]

No.

b(n+1) = 2 + ∏(k from 0 to n) b(k)

So b(1) = 2 + ∏(k from 0 to 0)b(k) = 2 + b(0) = 2 + 3 = 5.

Can you now work out b(2), b(3), b(4) and b(5)? Try and see the pattern, then I (or someone else) can guide you through the induction if you still have problems.

then
b(2) = 2 + ∏(k from 0 to 1)b(k) = 2 + b(0)*b(1) = 2 + 3*b(1)

b(3) = 2 + ∏(k from 0 to 2)b(k) = 2 + b(0)*b(1)*b(2) = 2 + 3*b(1)*b(2)

b(4) = 2 + ∏(k from 0 to 3)b(k) = 2 + b(0)*b(1)*b(2)*b(3) = 2 + 3*b(1)*b(2)*b(3)

b(5) = 2 + ∏(k from 0 to 4)b(k) = 2 + b(0)*b(1)*b(2)*b(3)*b(4) = 2 + 3*b(1)*b(2)*b(3)*b(4)

right ?

 

[Curious3141]

then
b(2) = 2 + ∏(k from 0 to 1)b(k) = 2 + b(0)*b(1) = 2 + 3*b(1)

b(3) = 2 + ∏(k from 0 to 2)b(k) = 2 + b(0)*b(1)*b(2) = 2 + 3*b(1)*b(2)

b(4) = 2 + ∏(k from 0 to 3)b(k) = 2 + b(0)*b(1)*b(2)*b(3) = 2 + 3*b(1)*b(2)*b(3)

b(5) = 2 + ∏(k from 0 to 4)b(k) = 2 + b(0)*b(1)*b(2)*b(3)*b(4) = 2 + 3*b(1)*b(2)*b(3)*b(4)

right ?

Yes, but calculate them (get the final numbers).

You should be able to make out the pattern clearly by b(4). b(5) is a little large, so you may not want to bother with that.

 

[maxmilian]

Yes, but calculate them (get the final numbers).

You should be able to make out the pattern clearly by b(4). b(5) is a little large, so you may not want to bother with that.

right.

b(2) = 17
b(3) = 257
b(4) = 65537

as far as a pattern goes for b(n) , I think I have a good idea (Fermet)

 

[Curious3141]

right.

b(2) = 17
b(3) = 257
b(4) = 65537

as far as a pattern goes for b(n) , I think I have a good idea (Fermet)

Yes, they are Fermat numbers. Now prove it by induction.

 

[maxmilian]

Yes, they are Fermat numbers. Now prove it by induction.

is recursion not a part of induction ?

I might have misunderstood the "determine the closed expression - without using recursion" wrong. but if I wanted to prove it by induction. I would;

1. prove the basis ;

b(0)=2^(2^0) +1 = 3 , true , basis proven.

2. prove inductionstep

b(n) -> b(n+1)
b(n) = 2^(2^n) +1 -> b(n+1)=2^(2^n+1) +1
b(1) = 2^(2^1) +1 = 5 -> b(1+1)2^(2^1+1)+1 = 17

both n and n+1 is true, so I have proven it for both n and n+1 - right ?

 

[Curious3141]

is recursion not a part of induction ?

What I mean is that you need to prove the closed form expression by mathematical induction. You've only inferred a pattern by observation, but you haven't rigorously proven it.

Of course, you need to use the recursive relation in your proof. But it needs to be a formal inductive proof, starting with an inductive hypothesis.

 

[Curious3141]

is recursion not a part of induction ?

I might have misunderstood the "determine the closed expression - without using recursion" wrong. but if I wanted to prove it by induction. I would;

1. prove the basis ;

b(0)=2^(2^0) +1 = 3 , true , basis proven.

2. prove inductionstep

b(n) -> b(n+1)
b(n) = 2^(2^n) +1 -> b(n+1)=2^(2^n+1) +1
b(1) = 2^(2^1) +1 = 5 -> b(1+1)2^(2^1+1)+1 = 17

both n and n+1 is true, so I have proven it for both n and n+1 - right ?

Let P(n) be the proposition that b(n) = 2^(2^n) + 1. This is the inductive hypothesis which you start by assuming.

From this, you need to establish that P(n+1) is true, i.e. that b(n+1) = 2^(2^(n+1)) + 1.

This needs to be an algebraic (symbolic) proof. Just verifying it for certain numerical n's is not sufficient.

 

[maxmilian]

Let P(n) be the proposition that b(n) = 2^(2^n) + 1. This is the inductive hypothesis which you start by assuming.

From this, you need to establish that P(n+1) is true, i.e. that b(n+1) = 2^(2^(n+1)) + 1.

This needs to be an algebraic (symbolic) proof. Just verifying it for certain numerical n's is not sufficient.

right.
so I start with my hypothesis, then prove basis , then assume P(n) is true , then last prove P(n+1) is true. How do I prove P(n+1) is true?

 

[Curious3141]

right.
so I start with my hypothesis, then prove basis , then assume P(n) is true , then last prove P(n+1) is true. How do I prove P(n+1) is true?

Wanted to reply to this earlier, but a lot of things came up.

So assume P(n) is true. Hence you can write down b(n) = 2^(2^n) + 1

Now you have to use this given relation: b(n+1) = 2 + ∏(from 0 to n) b(k)

to somehow arrive at b(n+1) = 2^(2^(n+1)) + 1

which would establish P(n+1).

Here's a hint:

∏(from 0 to n) b(k) = b(n) * ∏(from 0 to (n-1)) b(k)

and

b(n) = 2 + ∏(from 0 to (n-1)) b(k),

so ∏(from 0 to (n-1)) b(k) = b(n) - 2

Can you put all that together and do the remaining algebra to prove the result?