Recurrence Relation - Self Doubt

Question

What is the recurrence relation for the  ternary strings of length $n$ which can be constructed using 0,1 or 2 only such that the  number of 0’s and number of 1's is odd ?

Comments

@Abhrajyoti00 
Though I have no specification in mathematics, my formal degrees are in computer science but whether it is physics, mathematics or computer science, generally, good institutes expects projects/assignments/thesis in latex. But it needs not be overleaf, any latex editing tool like Texmaker would work. These tools are also helpful for making good ppts, making good CVs (various templates are available), writing research papers etc. 

---

@ankitgupta.1729 and even wedding invitations :) 

And in GO PDFs images are done using Tikz package of Latex. This is the repository containing the templates we use. 

generally, good institutes expects projects/assignments/thesis in latex

In general good institutes expectstudents to use/good/best tools available (especially if free). “git” is one other example. Unfortunately if in an average engineering college a faculty tries to do this he/she will be elimiated by students and other teachers. I remember one of our B.Tech. faculty suggesting us to use latex and we were like “Word” works perfectly. At top universities students can’t escape like this.

---

@gatecse Sir, they are life skills :)

Answer 1

Let T(n) be the number of ternary strings of length n in which the number of 0's and the number of 1's is odd.

Consider the last digit of a ternary string of length n:

• If the last digit is 0, then the remaining n-1 digits must have an even number of 0's and an odd number of 1's.
• If the last digit is 1, then the remaining n-1 digits must have an odd number of 0's and an even number of 1's.
• If the last digit is 2, then the remaining n-1 digits can have any combination of 0's and 1's.

Therefore, we can write the recurrence relation as follows: T(n) = 2T(n-2) + 3^(n-1)

The first term in the recurrence relation corresponds to the cases where the last digit is either 0 or 1, and the remaining n-1 digits satisfy the conditions of the problem. There are 2 ways to choose whether the last digit is 0 or 1, and the number of valid strings of length n-2 is T(n-2).

The second term corresponds to the case where the last digit is 2, and the remaining n-1 digits can have any combination of 0's and 1's. There are 3 possible digits that can be used for each of the n-1 positions, so the total number of valid strings of length n with a last digit of 2 is 3^(n-1).

The initial conditions for the recurrence relation are: T(0) = 0 T(1) = 0 T(2) = 2 (the two valid strings are "01" and "10")

Using the recurrence relation and the initial conditions, we can compute T(n) for any positive integer n.

Comments

If T(n) represents ternary strings of length n having odd number of 1s & 0s then how can you write T(n-2) [1st term of the RHS of your recurrence relation] as the count of ternary strings having even no. of 1s & odd no. of 0s and vice versa?

Also the only place where T(n-1) can be written is the 2nd term of the recurrence relation.

Correct me if I'm wrong somewhere.