229k views
2 votes
Solve the recurrence relation sn = 2sn-1, s0 = 1.

User Franksort
by
7.8k points

1 Answer

6 votes

Final answer:

To solve the recurrence relation s_n = 2s_{n-1} with s_0 = 1, one iterates from the base case to find that the nth term is given by s_n = 2^n.

Step-by-step explanation:

The recurrence relation given is sn = 2sn-1, with the initial condition s0 = 1. This is a simple geometric progression where each term is twice the previous term. To solve the recurrence, we can iterate the relation starting from the base case:

  • s1 = 2s0 = 2 × 1 = 2
  • s2 = 2s1 = 2 × 2 = 4
  • s3 = 2s2 = 2 × 4 = 8

Continuing this process, we can see that the nth term is given by sn = 2n.

This sequence is an example of exponential growth, commonly found in contexts like population dynamics (Nn = N02n) and light refraction (Snell's law), albeit unrelated to the recurrence relation itself.

User Alaboudi
by
7.3k points
Welcome to QAmmunity.org, where you can ask questions and receive answers from other members of our community.

9.4m questions

12.2m answers

Categories