L_n에 대한 반복 수식은 무엇입니까? L_n은 인접한 0과 2가없는 집합 {0, 1, 2}의 단어가있는 문자열 수 (a_1, a_2, ..., a_n)입니다.

대답:

# L_1 = 3, L_2 = 7, L_ (n + 1) = 2L_n + L_ (n-1) ""(n> = 2) #

설명:

먼저 우리는 # L_1 # 과 # L_2 #.

# L_1 = 3 # 단 3 개의 문자열이 있기 때문에: #(0) (1) (2)#.

# L_2 = 7 #인접한 0과 2가없는 모든 문자열은 다음과 같습니다.

#(0,0),(0,1),(1,0),(1,1),(1,2),(2,1),(2,2)#

이제 우리는 재발을 발견 할 것입니다. # L_n # # (n> = 3) #.

문자열이로 끝나는 경우 #1#, 우리는 그 후에 어떤 말도 할 수 있습니다.

그러나 문자열이로 끝나는 경우 #0# 우리는 단지 넣을 수 있습니다 #0# 또는 #1#.

Similary, 문자열이 끝나는 경우 #2# 우리는 단지 넣을 수 있습니다 #1# 또는 #2#.

방해 # P_n, Q_n, R_n # 없는 문자열의 수 #0# 과 #2# 인접한 위치에 있고 #0,1,2#로 나타났다.

# L_n, P_n, Q_n # 과 # R_n # 아래의 재발행을 따르십시오:

# L_n = P_n + Q_n + R_n # (나는)

# P_ (n + 1) = P_n + Q_n # (ii)

# Q_ (n + 1) = P_n + Q_n + R_n #(# = L_n #) (iii)

# R_ (n + 1) = Q_n + R_n # (iv)

(ii), (iii) 및 (iv)의 합계를 볼 수 있습니다. #n> = 2 #:

# L_ (n + 1) = P_ (n + 1) + Q_ (n + 1) + R_ (n + 1) #

# = 2 (P_n + Q_n + R_n) + Q_n #

# = 색상 (파란색) (2L_n) + 색상 (빨간색) (L_ (n-1)) # ((i) 및 (iii)을 사용하여)