Proving the recursive formula for "Virahanka Numbers"

Question

So apparently Virahanka was an Indian mathematician that, in a way, discovered the Fibonacci sequence 500 years before Fibonacci. He was interested in finding the number of patterns of short syllables ($S$) and long syllables ($L$). We let $p$ be a pattern, that is, an ordered sequence of $S$'s and $L$'s, we assign a value of $1$ to $S$ and $2$ to $L$, and so the length of $p$ is: # of $S$'s + $2$(# of $L$'s). We let $P_n$ denote the set of patterns of length $n$, and let $v_n=|P_n|$

e.g. $P_0=\emptyset$, $P_1=${$S$}, $P_2=${$SS,L$}, $P_3=${$SSS,SL,LS$} and $v_0=1$, $v_1=1$, $v_2=2$, $v_3=3$

How can I prove that $v_n=v_{n-1}+v_{n-2}$

I honestly have no idea where to begin.

Of all of the patterns in $P_n$, how many end with a short symbol? How about with a long symbol? — Mike Earnest, Mar 02 '15 at 05:37
There are $n-1$ short syllables and $n-2$ long syllables, I see, that's helpful. Thanks. — user220329, Mar 02 '15 at 05:49

score 2 · Accepted Answer · answered Mar 02 '15 at 05:37

2

Each element in $P_n$ is gotten from an element in $P_{n-1}$ by adding an $S$ or from an element in $P_{n-2}$ by adding an $L$.

answered Mar 02 '15 at 05:37

marty cohen

107,799

Also helpful, thanks! – user220329 Mar 02 '15 at 05:49

kyramichel · Answer 2 · 2021-02-23T22:04:20.923

0

More exactly, the elements of vn are obtained from elements of vn−1 by prefixing an S + elements of vn−2 by prefixing an L.

For example, v4 = {LL, LSS, SSL, SLS, SSSS} = {LL, LSS} + {SSL, SLS, SSSS} where:

{LL, LSS}: L prefixed to each item of v2 = {L, SS}

{SSL, SLS, SSSS}: S prefixed to each item of v3 = {SL, LS, SSS}.

See code

edited Feb 23 '21 at 22:04

answered Jan 31 '21 at 06:26

kyramichel

101

Proving the recursive formula for "Virahanka Numbers"

2 Answers2