Answer: $a_n=\frac{2}{5}(9^n-(-1)^n)$

I got $\frac{2}{5}(9^n-(-1)^n)$

recursion, $F_n=8F_{n-1}+9F_{n-2}, F_1=4, F_2=32$

lmao I posted this first but mine was deleted

Ok what am I even doing.....when I was solving for f(3), I thought 32*8=252.... this is just sad

Th3Numb3rThr33 wrote: For each positive integer $n$, find the number of $n$-digit positive integers that satisfy both of the following conditions: no two consecutive digits are equal, and the last digit is a prime. This looks like HMMT...

Oh my god...it turns out I was literally one step from solving #2 as well, so 14 --> 0

Rip, I forgot first digit is not 0...

How many points is it if i got that $a_{n}=8a_{n-1}+9a_{n-2}$??????

bogstop320 wrote: How many points is it if i got that $a_{n}=8a_{n-1}+9a_{n-2}$?????? 1 or 2 for nontrivial progress. It's a pretty important step, but not that hard to see, so I'm not completely sure

When you forget that $\frac{4}{10} = \frac{2}{5}$...

nukelauncher wrote: When you forget that $\frac{4}{10} = \frac{2}{5}$... i dont think they will take off points for that

why is jmo stealing from aime now

yeah @above tbh this would make a AIME #9 or #10.

Would I lose points for not using the (-1)^n thing, and instead said if n is odd it's plus and even is minus?

bogstop320 wrote: How many points is it if i got that $a_{n}=8a_{n-1}+9a_{n-2}$?????? That's a lot actually, because the rest is a standard characteristic polynomial to solve the recurrence, which is very straightforward if you've seen it before.

Let $f(n)$ be the answer $f(n)=8*f(n-1)+9*f(n-2)$ because there are 8 possible digits to add to anything in $f(n-1)$ and you can also add $10,20, 30,...,90$ to anything in $f(n-2)$ $f(n)-8f(n-1)-9f(n-2)=0$ Assume that $f(n)=c^n$ $c^n-8c^{n-1}-9c^{n-2}=0$ $c^2-8c-9=0$ $c=-1,9$ So $f(n)=a(-1)^n+b*9^n$ $f(1)=4,f(2)=32$ So solve to get $a=-\frac{2}{5},b=\frac{2}{5}$ so the answer is $-\frac{2}{5}(-1)^n+\frac{2}{5}*9^n$

S.Das93 wrote: still harder than this yrs j1 this is not true

ihatemath123 wrote: S.Das93 wrote: still harder than this yrs j1 this is not true yeah dont take my word for it i have a major skill issue

We claim that $a_n = 8a_{n-1} + 9a_{n-2}.$ Suppose that the second digit of $a_n$ is non-zero. Then there are $8$ different choices for the first digit and $a_{n-1}$ possible numbers for rest of the digits, including the second digit. Hence, the number of possible positive integers that has a prime last digit and no two consecutive digits are equal with the second digit being non-zero is $8a_{n-1}.$ Now, suppose that the second digit of $a_n$ is zero. Then there are $9$ different choices for the first digit and $a_{n-2}$ possible numbers for rest of the digits. Hence, the number of possible positive integers that has a prime last digit and no two consecutive digits are equal with the second digit being zero is $8a_{n-2}.$ Therefore $a_n = 8a_{n-1} + 9a_{n-2}$ and thus our claim is true. This is a linear homogenous recurrence relation and hence its characteristic polynomial is $x^2-8x+9 = (x-9)(x+1) = 0.$ Clearly, $a_1 = 4$ and $a_2 = 32.$ Thus, \[9c_1 - c_2 = 4\]\[81c_1 + c_2 = 32\]Solving this system gives $c_1 = \frac{2}{5}$ and $c_2 = -\frac{2}{5}$ so the answer is $a_n = \boxed{ \frac{2}{5}\left(9^n-(-1)^{n}\right)}.$

Let $a_n$ denote the number of positive integers with $n$ digits such that no two consecutive digits are equal and the last digit is prime. Let $b_n$ denote the number of positive integers with $n$ digits such that no two consecutive digits are equal and the last digit is not prime. It follows that $$a_n + b_n = 9^n$$ To get our second recursive relation, we consider a good $n-1$ digit number. If the last digit is not prime, then we have 4 choices for the last digit. If the last digit is prime, then we have 3 choices for the last digit. It follows that $$a_n = 3a_{n-1}+4b_{n-1}$$With some manipulations left to the reader we eventually recover $$a_n = 8a_{n-1}+9a_{n-2}$$with initial conditions $a_0 = 0$ and $a_1 = 4$. We then extract $$a_n = \frac{2}{5}(9^n-(-1)^n)$$

We, let $a_n$, be the number of $n-$ digit positive integers, that satisfy these conditions. Now, we have $a_1=4$, and $a_2=32.$ We, will take casework on the second digit, because if the second digit is $0,$ then the first digit has $9,$ choices, but if it is nonzero, the second digit has $8$, choices. Now, if the second digit is $0,$ we have $a_{n-2}$, ways to arrange the rest of the numbers, because there are $n-2$, digits left, hence, in this case, we have $9\cdot a_{n-2}$, possibilities. Now, if the second digit is nonzero, we have $a_{n-1}$, ways to arrange the rest of the digits, note that this is different, then when the second digit is nonzero, because, we now, have more options for the second digit. So, we have the recursion, $a_n=8\cdot a_{n-1}+9\cdot a_{n-2},$ also $a_1=4$, and $a_2=32.$ Claim: This, closed form, is $\frac{2}{5}\cdot (9^n-(-1)^n).$ Proof: We, use induction. The base, case, when $n=1$, gives us $\frac{2}{5}\cdot 10=4,$ as expected. The, inductive step, first we assume, that $a_n=\frac{2}{5}9^{n}-\frac{2}{5}(-1)^{n}$, and $a_{n+1}=\frac{2}{5}9^{n+1}-\frac{2}{5}(-1)^{n+1}$, now we can bash, this, out for $a_{n+2}$, using the recursion, we found, so in this case $9\cdot(\frac{2}{5}9^{n}-\frac{2}{5}(-1)^{n})+8\cdot (\frac{2}{5}9^{n+1}-\frac{2}{5}(-1)^{n+1})=a_{n+2}=\frac{2}{5}9^{n+2}-\frac{2}{5}(-1)^{n+2}$, we can do all this algebra, and we get that this induction holds, hence, the answer is $\boxed{\frac{2}{5}(9^n-(-1)^n)}.$

First we can find the answer for numbers up to $n$ digits (including those with less than $n$ digits) is $4\cdot9^{n-1}$ by induction. Next if we define the required answer for each $n$ to be $a_n$, we can get the recurrence sequence $a_n=4\cdot9^{n-1}-a_{n-1}$. Inducting on this gives that $a_n=\dfrac{2}{5}(9^n-(-1)^n)$, which is our answer. Full proof here: https://infinityintegral.substack.com/p/usajmo-2018-contest-review

Let $a_n$ be the amount of $n$-digit numbers satisfying the given conditions. Notice by appending a leading $0$ to all $(n-1)$-digit numbers, we get that \[a_n+a_{n-1} = 4 \cdot 9^{n-1}.\] Shifting $n$ to $n-1$, we get \[a_{n-1}+a_{n-2} = 4 \cdot 9^{n-2},\] and then dividing the two gives \[\frac{a_n+a_{n-1}}{a_{n-1}+a_{n-2}} = 9\]\[\implies a_n = 8a_{n-1}+9_{n-2}.\] Solving the characteristic polynomial shows us that \[a_n = c_1 9^n + c_2 (-1)^n.\] Now, using $a_0=0$ and $a_1=4$, we get that \[a_n = \boxed{\frac{2}{5} (9^n-(-1)^n)}.\]

We will solve using recursion. Firstly, consider the sequences which are in the form $p0q\ldots$ - we can think about these by considering only the part from $q$ onward, and then there are $9$ ways to choose $p$. Next, consider the sequences do not have a zero as their second digit and are in the form $prq\ldots$ - we can think about these by considering only the part from $r$ onward, and then there are $8$ ways to choose $p$. Thus, we can create the recursion $a_n = 8a_{n-1}+9a_{n-2}$ where $a_n$ is the amount of working ways for an $8$-digit number. The characteristic polynomial for this recursion is $x^2-8x-9 = 0$, which has roots $x = -1, 9$ and thus we have $a_n = p \cdot (-1)^n + q \cdot 9^n$. We know that $a_1 = 4$ and $a_2 = 32$, so $-p+9q = 4, p+81q = 32$. Then we get $p = -\frac{2}{5}, q = \frac{2}{5}$, so the answer is $a_n = -\frac{2}{5} \cdot (-1)^n + \frac{2}{5} \cdot 9^n$ ways for an $n$-digit number.

MAA POV: this is a really nice prob for AIME #1 (rip MAA)

We use recursion. Let $a_n$ be the number of $n$-digit positive integers that satisfy the conditions. We can construct such an integer in two ways. First, if the second leftmost digit is not $0$, we can take an $(n-1)$-digit positive integer that satisfies the conditions and add one of $8$ possible digits to the front of that $(n-1)$-digit integer. This gives us $8a_{n-1}$ possible integers. Next, if the second leftmost digit is $0$, then we can take an $(n-2)$-digit positive integer (because the digit to the right of that $0$ must be nonzero) and add one of $9$ possible (nonzero) digits in front of the $0$, creating a valid $n$-digit integer. This gives us $9a_{n-2}$ possible integers. Thus, we obtain the recursion $a_n = 8a_{n-1} + 9a_{n-2}$. Note that $a_1=5$ and $a_2=32$, so we can solve (via characteristic polynomial) to get $a_n=\frac 25\cdot (9^n-(-1)^n)$. $\blacksquare$

Let $a_n$ be the answer for a given $n$. By caseowrk on the first few digits (namely, if they are $0$ or not), it's not hard to see that $a_n=8a_{n-1}+9a_{n-2}$ with characteristic roots $9$ and $-1$. So our answer is in the form of $a_n = c_1 \cdot 9^n + c_2 \cdot (-1)^n$ plug in initial conditions blah blah $a_n = \boxed{\frac25(9^n - (-1)^n)}$

unique solution

We claim the answer is $\boxed{\frac{2}{5}(9^n - (-1)^n)}$. Let $F_n$ be the number of strings of length $n$ with no $2$ consecutive digits equal, the first digit is nonzero, and the last digit is a prime. Let $Q_n$ be the number of strings of length $n$ with no $2$ consecutive digits equal, the first digit equal to $0$, and the last digit a prime. It is easy to see that $F_1 = 4, Q_1 = 0$, and $F_2 = 32, Q_2 = 4$. We get the recursive equations \[F_n = 8F_{n-1} + 9Q_{n-1}\]\[Q_n = F_{n-1}\]Substituting the second equation into the first, \[F_n = 8F_{n-1} + 9F_{n-2}\]which has the characteristic polynomial \[\lambda^2 - 8 \lambda - 9 = (\lambda - 9)(\lambda +1)\]Therefore, \[F_{n} = A \cdot 9^n + B \cdot (-1)^n\]Plugging in the values for $n =1 , 2$ and solving we get $(A,B) = (\frac{2}{5}, - \frac{2}{5})$, and we are done.