Counting Features of Subsets 
*

*How many subsets of $\{1,2,3,4,5,6,7\}$ are there that do not contain two consecutive integers?  Include the empty set, too.

*For any nonempty set $T$ whose elements are positive integers, define $f(T)$ to be the square of the product of the elements of $T$. For example, if $T=\{1,3,6\}$, then $f(T)=(1\cdot 3\cdot 6)^2 = 18^2 = 324$.
Consider the nonempty subsets $T$ of $\{1,2,3,4,5,6,7\}$ that do not contain two consecutive integers. If we compute $f(T)$ for each such set, then add up the resulting values, what do we get?
Is there a major induction that I'm missing because I don't see any.  Any answer is greatly appreciated.
 A: Let $S_n$ be the collection of subsets of $\lbrace 1,\dots,n \rbrace$ that do not contain two consecutive integers.
$S_0$ is the set $\lbrace \emptyset \rbrace,$ and $S_1$ is $\big\lbrace \emptyset, \lbrace 1 \rbrace \big\rbrace.$
For $n\ge 2,$  $S_{n}=S_{n-1} \bigcup \big\lbrace X \cup \lbrace n \rbrace \vert X \in S_{n-2}\big\rbrace.$
That's enough to get an induction going to compute the numbers that you're interested in.
(Thank you to @Shagnik for pointing out that I had misread the problem as asking to count only non-empty subsets.)
A: The number of subsets of $\{1,2,\ldots,7\}$ without two consecutive integers is the same as the number of strings with length $7$ over the alphabet $\Sigma=\{0,1\}$ without two consecutive $1$s (if we consider some element, we "mark it" with a $1$). Let $S_n$ be the number of strings with length $n$ with the same property. We have $S_1=2$, $S_2=3$ and $S_{n}=S_{n-1}+S_{n-2}$ for any $n\geq 3$, since a valid string may start only with a $0$ or with $10$. It follows that $S_n=F_{n+2}$ and $S_7=F_9=\color{red}{34}$.
For part $2$, there is Marko Riedel's hint. Let we say that a set is special if it does not have consecutive elements and let
$$ A_n = \sum_{\substack{A\subset\{1,\ldots,n\}\\A \text{ special}}}\prod_{a\in A}a^2. $$
There are just two cases: $n$ is an element of a special set in $\{1,2,\ldots,n\}$ or it is not. According to such observation, we have
$$ A_1=1,\quad A_2 =5,\qquad A_{n}=A_{n-1}+n^2(1+A_{n-2}) $$ 
hence $A_7=\color{red}{40319}$.
