Online Course Discussion Forum

Math Challenge II-A Combinatorics

 
 
Picture of Neo Liang
Math Challenge II-A Combinatorics
by Neo Liang - Wednesday, 27 November 2019, 10:49 AM
 

Lecture 7, Problem 7.6b

I got $a_n=2 \cdot 3^{n-1} + a_{n-1}$ because you can separate the problem into two cases- the case where the last friend doesn't go to the reception and if he goes to the reception. If he goes to the reception, it is $2 \cdot 3^{n-1}$ because the last friend has 2 choices and the rest have 3 choices. If he doesn't go to the reception, it is $a_{n-1}$. Using the Sum Rule, you get $a_n=2 \cdot 3^{n-1} + a_{n-1}$.

 
Picture of Areteem Professor
Re: Math Challenge II-A Combinatorics
by Areteem Professor - Wednesday, 27 November 2019, 5:33 PM
 

Your answer is correct. Note there is no unique way to write a recursive formula for a given sequence.

To see that both recursive formulas coincide (yours and the one in the solution): assume $2\cdot 3^n + a_n = 3 \cdot a_n + 2$, then $$\begin{aligned}2\cdot 3^n + a_n &= 3 \cdot a_n + 2 \\ 2\cdot a_n + 2 &= 2\cdot 3^n \\  a_n + 1 &= 3^n \\ a_n &= 3^n -1.\end{aligned}$$ Note we know this last equation is true, since it is the answer for part (a), so both formulas determine the exact same sequence.

Also, remember that when giving a recursive formula you must also provide the first value of the sequence.