# mathematical induction; recursive definition of the set of all positive integers; $7^{2n+1} + 6^{n+2}$ divisible by $43$

It says here: give a recursive definition of the set $P$ of all positive integers greater than $1$, whereby I'm not certain whether the answer is:

Rule 1: $P$ is greater than $1$

Rule 2: If $x$ is in $P$ then $x + 1$ is also in $P$

Rule 3: No other words are in $P$

I'm just not sure if whether I missed anything.

Also, I have to formulate an appropriate induction principle where I said: if a subset of $P$ contains an integer greater than $1$ and is such that it contains $x + 1$ whenever it contains $x$, then that subset equals $P$.

Am I on the right track and where did I go wrong?

Following those problems was the final one:

Prove $7^{2n+1} + 6^{n+2}$ is divisible by $43$ for $n \geq 1$, where I said:

check whether $1$ is an element where the answer I got was $343 + 216$ which is divisible by $43$ and equals $13$. Then I said: assume $k$ is an element and check whether $k + 1$ is divisible by $43$ and I got stuck at $7^{2k+3} + 6^{k+3}$... What am I not seeing and where can I learn more about proving equations to belong to sets via mathematical induction?

-

## migrated from cstheory.stackexchange.comMar 5 '13 at 8:11

This question came from our site for theoretical computer scientists and researchers in related fields.

$7^{2n+1}+6^{n+2}=49^n\times7+6^n\times 36=(43+6)^n\times 7+6^n\times 36$, and all that needs to be checked is that $(43+6)^n$ has the form $43k+6^n$. –  Andres Caicedo Jul 27 '13 at 2:52

For a recursive definition you need:

• a base case R1: $1\in P$
• an inductive clause R2: if $x\in P$ then $x+1\in P$
• and qn extremal clause R3: P is the smallest set satisfying R1 and R2.

Your base case was wrong, the set $S=[5,6,7,...]$ answer to Rules 1,2 and 3 but $P\neq S$.

Same problem for the subset, you have to ensure that the case basis is satisfied, hence that 1 is in the subset: "if a subset of P contains 1 and is such that it contains x + 1 whenever it contains x, then that subset equals P."

For the last problem. You check the base case like you did. And then you assume k is an element (like you did) so you know that: $$7^{2k+1}+6^{k+1}\equiv 0[43]$$ hence there exists $a,b$ such that $a+b=43$ and: $$7^{2k+1}\equiv a[43]$$ $$6^{k+1}\equiv b[43]$$ it follows that $$7^{2(k+1)+1}=7^2*7^{2k+1}\equiv 49a[43]\equiv 6a [43]$$ $$6^{(k+1)+1}=6*6^{2k+1}\equiv 6b[43]$$ hence that $$7^{2(k+1)+1}+6^{(k+1)+1}\equiv 6(a+b)[43]$$ and you conclude by saying that $a+b\equiv 0[43]$ hence $6(a+b)\equiv 0[43]$.

Hence k+1 is also an element.

Hope it helps.

-