MathDB

Lily pads

1,2,3,\ldots

lie in a row on a pond. A frog makes a sequence of jumps starting on pad

1

. From any pad

k

the frog jumps to either pad

k+1

or pad

k+2

chosen randomly and independently with probability

\tfrac12

. The probability that the frog visits pad

7

\tfrac pq

, where

p

and

q

are relatively prime positive integers. Find

p+q

Problem Statement