Recurrence Relation - Self Doubt

https://math.stackexchange.com/questions/2138129/recurrence-relation-for-the-number-of-ternary-strings-of-length-n-with-an-eve

like this @gatecse

@AKASH VISIONGATE I am not able to simplify G(x) further. 

G(x) = 2x + 6x^2 + 20x^3 + 60x^4 + 182x^5 + 546x^6 +…… This is what I am getting. Can you help me simplify this?

I tried to make it like a Recurrence relation from your generating function and i got below relation

can you verify it?

i might be wrong

@AKASH VISIONGATE

@Sunnidhya Roy

@viniit first one will be for even second one for odd.

I calculated for length 8 got 1640. 

Divisions for 8 are: (1 7) (7 1) (1 5) (5 1) (3 5) (5 3) (3 3) (1 3) (3 1) (1 1). If we find out all possible strings it adds upto 1640. And it is satisfying for length 9 as well.

@viniit how did you reach this relation? Just by analyzing the sequence or you did any calculation? Awesome 🤩.

sir i just generalized the pattern made by @Sunnidhya Roy

Great Thanks @viniit.

@gatecse Sir is our analysis correct for the given question?

thanks @Sunnidhya Roy @viniit its an excellent question .  can we generalize in terms of formula means we can solve that recurrence relation and we can get formula .

Sorry I din't get you @AKASH VISIONGATE generalization into which formula?

https://math.stackexchange.com/questions/2138129/recurrence-relation-for-the-number-of-ternary-strings-of-length-n-with-an-eve

in this you can how they convert the recurrence into the (3^n +1)/2 so can we convert this sum into same like that !!!!

@AKASH VISIONGATE I am not sure, we can follow Recurrence tree method and there will be two kinds of Recurrence tree one for odd and another for even, need to look into that, but the above answer doesnot seem correct, you can check for lengths 1 2 and 3 the summation is 8 whereas the formula they have given will give 14.

@AKASH VISIONGATE Here you have it: combinatorics - Compute the number of n-tuples that contains odd numbers of 0's and 1's, using generating function - Mathematics Stack Exchange

@AKASH VISIONGATE The eqn can be converted to generalized form by first finding the complementary function, then finding the particular solution

that is the most mind blowing and I got the somewhere same recurrence as it is mentioned into this post......but need to look more!!!..... https://math.stackexchange.com/questions/2802377/compute-the-number-of-n-tuples-that-contains-odd-numbers-of-0s-and-1s-using-g ,  @Sunnidhya Roy @viniit @Abhrajyoti00 @gatecse thankyou all!!!!!

@AKASH VISIONGATE :) 

@viniit Recurrence is this right?

$T(0) = T(1) = 0$

$T(n) = 3T(n-1) + 2 \times ((n+1)\mod2); \quad n > 1$

Can any one logically explain the reasoning for the $2 \times [(n+1)\mod 2]$ term? Only someone good in the formation of recurrence relations can do it. 

Formation of $3T(n-1)$ is also interesting. From a ternary string of length $n-1$ with odd number of $0s$ and $1s$ we can get a ternary string of length $n$ again with odd number of $0s$ and $1s$ only by adding a single $2.$ How does adding a single $2$ triple the number of possible strings?

@gatecse Sir 2*[(n+1) mod 2] will evaluate to 0 when n is odd as odd+odd(1) is even and mod 2 will evaluate to 0 so we have only 3T(n-1) and similarly will evaluate to 1 when n is even because for (even + 1) mod 2, mod 2 can have 2 values 0,1 as even number is already there it will contribute to 0+1 mod 2 which will evaluate to 1 and so we have 3T(n-1) +2.

As for 3T(n-1) logic,

Sir Say we take length 2 strings i.e 01 and 10

​​​​​​Now for Length 3 strings we can place 2 in 3 places for each string i.e 201 021 012 and in similar way for 10 we can place 2 in 3 places 210 120 102. Hence we have 3T(n-1)

Is this correct way to think @gatecse Sir?

Sir when we are dividing the strings into groups and evaluating the number of arrangements we can observe these:

If we have say n=3 we can’t divide the string into 2 odd number divisions of 0 and 1 right. So numerator will be 3! but denominator cannot be 3! and hence the factor 3 of the numerator cannot be cancelled. So 3 mod 3 = 0

Now for n=4 we can divide the string into 2 odd number divisions for 0 and 1 which are 1 3, 3 1 and now numerator for both will be 4! and one of the denominators will be 3! thus cancelling out the 3 factor from the numerator and 4 mod 3 = 1 and we have 2 such strings and hence 2 is added.

In the similar way if we take n=5 we will have divisions 1 3, 3 1, 1 1 for each of them numerator will be 5! and one of the denominators for each will be 3! which will cancel out the 3! from the numerator leaving 20 for each of the 3 divisions and 20 mod 3 = 2 and we have 3 of them so 6 mod 3 = 0 and hence for n=5 we have the total number as divisible of 3.

Then if we take n=6 we have divisions 1 5, 5 1, 3 3, 1 3, 3 1, 1 1 for which numerator will be 6! and 3 3 divisions will remove 3! and 6 from the numertor leaving 4*5= 20 and 20 mod 3=2, for rest of the divisions numerator will contain a multiple of 3 so only 3 3 division will contribute for the additional 2.

@gatecse Sir Is this correct?

The condition to be satisfied here is “odd number os 0s and 1s” and lets say a string is valid if the condition is satisfied.

From any valid string of length “n-1” can we can get 3 valid strings of length n, by adding a “2” at different positions. 

Lets take $n=4.$ Valid strings of length $3$ are

$012, 021, 102, 120, 210, 201$

• $012$ can give $3$ valid strings of length $4$ like $2012, 0212, 0122$
• $021$ can give $2$ valid strings of length $4$ like $2021, 0221$
• $102$ can give $3$ valid strings of length $4$ like $2102, 1202, 1022$
• $120$ can give $2$ valid strings of length $4$ like $2120, 1220$
• $210$ can give $3$ valid strings of length $4$ like $2210, 2120, 2102$
• $201$ can give $1$ valid strings of length $4$ like $2201$

Thus we got $14$ valid strings of length $4.$

From an invalid string of length “n-1” we can get a valid string of length n, by adding a “0” or “1”. For this to happen the original string must have

• An even number of 2’s
• An odd number of 0s and an even number of 1s or vice versa

For $n=4,$ we get $6$ valid strings by adding $0/1$ to the below $6$ invalid strings of length $3:$

$011, 110,010,101,001,100$

Valid strings of length $4: 0111, 1101,0100,1011,0010,1000$

Unfortunately I’m not sure if this analysis can lead to the recurrence relation. 

@AKASH G and @Sunnidhya Roy

This is your closed form expression for the given problem:

1. For $n \geq 6 $ and $n=even$

$$T(n) = 2^{n-1} + \Sigma_{i=n-3}^{i=i-2 \  \& \  i\geq 3} \ \left(\frac{n(n-1)...(i+2)}{(n-i-1)!}\right)2^{i} + 2 \Sigma_{i=1}^{n-1} \ i$$

2. For $n \geq 7 $ and $n=odd$

$$T(n) = n \times 2^{n-2} + \Sigma_{i=n-4}^{i=i-2 \  \& \  i\geq 3} \ \left(\frac{n(n-1)...(i+2)}{(n-i-1)!}\right)2^{i} + 2 \Sigma_{i=1}^{n-1} \ i$$

This is from my observation for the given problem and I can provide proof for it if you want. You can further simplify it if you want. Since, the given recurrence is promising but it is not proved, So, I have not taken it.

@gatecse if you observe in the @Sunnidhya Roy’s image,  “+2”  comes when $n$ is even. because for even $n$ you have to append some pairs, for example, when $n=6,$ $(1,5),(5,1),(3,3)$ are added and same for other even values of $n.$ But when $n$ is odd then you don’t have to add pairs, you just have to append $2s.$

Now, when $n$ is even, the value of the newly added pairs are: $\binom {n}{1}+ \binom {n}{3}+ \binom {n}{n-1} = 2^{n-1} = 2^{n-1}\ – \ 2 + 2 =2(2^{n-2}-1) + 2 .$ Now, for even $n,$ $2^{n-2}-1$ is multiple of $3.$ You can prove it as: for even $n,$ and $n \geq 4$, $(n-2)$ is even and so, you can write it as $2^{2k} \  – \ 1 = 4^k – 1 = (1+3)^k – 1$ and now, use binomial expansion and you will get terms which are multiple of 3. Now, for other terms for $T(n)$ contains $3!,$ So, they are also multiple of 3 and so, you get terms multiple of 3 and added “+2” for even values of $n.$  

@ankitgupta.1729 great work. Are the limits of the summation correct? Please do share the proof - if you have on paper even a photo of it is fine. It can guide students interested in Mathematics. 

@ankitgupta.1729 Thankyou ,but still can you provide the logic behid this means how you have evaluated and reach at this conclusion.

@gatecse there is nothing typo in the formula. Sigma notation might confused you. When we write $\Sigma_{i=1}^{i=6}$ then it means $i=1,2,3,4,5,6.$ Here $\Sigma_{i=n-3}^{i=i-2 \& i \geq 3}$ means $i= (n-3), (n-5),(n-7)…,3$

So, Suppose, $n=12$ then $\Sigma_{i=n-3}^{i=i-2 \& i \geq 3}$ means $i= 9, 7,5,3$

I am giving some examples here:

$T(12) = 2^{11} + 2^9 * \frac{12*11}{2} + 2^7* \frac{12*11*10*9}{4*3*2} + 2^5* \frac{12*11*10*9*8*7}{6*5*4*3*2}$

$+ 2^3* \frac{12*11*10*9*8*7*6*5}{8*7*6*5*4*3*2} + 2 (11+10+9+...+1) $

$T(12) = 132860$

Similarly,

$T(13) = 13*2^{11} + 2^9* \frac{13*12*11}{3*2} + 2^7* \frac{13*12*11*10*9}{5*4*3*2} + 2^5* \frac{13*12*11*10*9*8*7}{7*6*5*4*3*2}$

$+ 2^3* \frac{13*12*11*10*9*8*7*6*5}{9*8*7*6*5*4*3*2} + 2 (12+11+10+9+...+1) $

$T(13) = 398580$

@AKASH G logic is not much difficult and you can make your own formula also if you analyze the things which are happening here from $n=2.$ The things which I have done, I can explain easily orally but writing here will take time, So, I will write the proof on Saturday or Sunday. 

Proof: https://www.overleaf.com/read/wdkcyqjkznvb

Let me know if anyone has any concern.

@ankitgupta.1729 Sir, amazing work! Every point is so nicely documented.

Typo: In $B) n=3$ some irredundant data is present.

P.s. Do Math Majors need to showcase their projects/assignments in Overleaf?

@ankitgupta.1729 Thanks for the notation explanation :) And the proof is fantastic and exactly what I was looking for and much easier to understand than the final recurrence 😄

@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 :)