I gave a slightly different strong induction proof to $3^{2n+1}+2^{n-1}$, is it correct?

78 Views Asked by At

I would like to know whether the following proof is correct and whether I also use correct notation.

We have the following formula: $A(n)=3^{2n+1}+2^{n-1}$. We want to know the whether $A(n)$ is divisible by 7 for all $n \geq 1$.

Here follows my proof:

Base case: $$3^{2(1)+1}+2^{1-1}=28$$ $\frac{28}{7}=4$ so the base case holds true.

We assume: $$A(k)=3^{2k+1}+2^{k-1} \space \text{so that} \space\space 7|A(k)\space \space\forall k \in \mathbb{N}, \space k \gt 1$$ Therefore:$$A(k+1)=3^{2(k+1)+1}+2^{(k+1)-1}$$ $$\dots$$ $$=9(3^{2k+1}+2^{k-1}) - 7(2^{k-1})$$

So: $\space\space 7|A(k)\space \space\forall k \in \mathbb{N}, \space k \gt 1$


My primary concern is with correctness of notation and whether my conclusion in the induction step ($\space \space9(3^{2k+1}+2^{k-1}) - 7(2^{k-1})\space\space$) is an ok solution. I noticed that I could've just factored $7(3^{2k+1})$ out and that might have been better but I wonder whether it matters for anything other than aesthetics.

3

There are 3 best solutions below

2
On BEST ANSWER

As a variant, write $$A_n=3\times 9^n+\frac 12 \times 2^n$$

Since $9,2$ are roots of the quadratic $$(x-9)(x-2)=x^2-11x+18$$ we deduce that we can define the $A_n$ recursively as $$A_1=28,\;A_2=245\quad \&\quad A_n=11A_{n-1}-18A_{n-2}$$

Since $7$ divides both $A_1,A_2$ it is clear (inductively) that $7\,|\,A_n$ for all $n\in \mathbb N$.

Note: It was clear without computation that there was such a two step recursion with integer coefficients, so even at the start all we had to do was to check the first two values. The argument doesn't depend on the exact values of the coefficients, just on the fact that they are integers.

0
On

That's how I would have done it, except that after writing that $$A(k+1)=9(3^{2k+1}+2^{k-1}) - 7(2^{k-1}),$$I would have added that this is $9A(k)-7(2^{k-2})$ and therefore, by the induction hypothesis, this number is a multiple of $7$.

0
On

Non-induction alternative: write $A(n)$ as: $$ 3(9^n-2^n)+7\cdot 2^{n-1} $$