Who is asking: Student
Level: Secondary

Question: A sequence s is defined recursively as follows:

s₀=1
s₁=2
s_k=2s_k-2 for all integers

- Compute s2,s3,s4... to guess an explicit formula for the sequence sk.

s₂=2(s_2-2)=2(s₀)=2(1)=2
s₃=2(s_3-2)=2(s₁)=2(2)=4
s₄=2(s_4-2)=2(s₂)=2(2)=4

I understand how to compute it, and I see the pattern is 1,2,2,4,4,8,8...and so on, but I am having trouble figuring out the formula... - Prove (through Induction) that the formula you obtained previously is correct.

If you could help me with this problem, I would very much appreciate it!!! Thank you

You're right about the sequence and you should notice also that the numbers are powers of 2 so your problem is to find an f(n) such that for your nth term s_n = 2^f(n).

Look at n= 3 & 4; you need 2² in both cases.
Look at n= 5 & 6; you need 2³ in both cases.
Look at n= 7 & 8; you need 2⁴ in both cases.

That is 3 & 4 correspond to 2;
5 & 6 correspond to 3;
7 & 8 correspond to 4; etc.

Doesn't the required exponent look about 1/2 of n? You might want to look at the integer part of (n+1)/2.

Penny