She searches for integer solutions and does not believe that the expressions given are integer. Mathematica is also not sure about that:

In[51]:= Clear[x, y]
x[n_] := 1/2 ((8 - 3 Sqrt[7])^n + (8 + 3 Sqrt[7])^n)
y[n_] := -(((8 - 3 Sqrt[7])^n - (8 + 3 Sqrt[7])^n)/(2 Sqrt[7]))

In[68]:= RootApproximant[x[#]] & /@ RandomInteger[{1, 30}, 17]

Out[68]= {2024, 2199950293420883836928, 2024, \
2325668404237133588966684445638656, 2261936092886171715528294400, \
2261936092886171715528294400, 8, 2261936092886171715528294400, 
 1/2 (134255446617603 + Sqrt[
    18024524946491071433658089473]), 574522862194843517270624305152, \
2024, 8193151, 2199950293420883836928, 558778713173023503941632, 8, \
37064767922732740871188780993740800, \
2325668404237133588966684445638656}

In[69]:= RootApproximant[y[#]] & /@ RandomInteger[{1, 30}, 17]

Out[69]= {12535521795, 194307, 765, 13625260145284696589750763520, \
13625260145284696589750763520, 3096720, 854931483328272233719136256, \
12192, 765, 831503053299319046144, 3183973182717, \
3460762433314345591306287316992, 786554688, \
854931483328272233719136256, 3, 3365924154344798473420800, 48}

and going up to 30 is not so far.

 In[72]:= FactorInteger[18024524946491071433658089473]
 Out[72]= {{151, 1}, {2577984271, 1}, {46302732029905513, 1}}
 In[73]:= 151 2577984271 == 46302732029905513
 Out[73]= False

Indeed not a square of something.

By the way, Martina, the solution appears exactly as announced by the manual:

In[48]:= Reduce[x^2 - 7 y^2 == 1 && x > 0 && y > 0, {x, y}, Integers]
Out[48]= C[1] \[Element] Integers && C[1] >= 1 && 
 x == 1/2 ((8 - 3 Sqrt[7])^C[1] + (8 + 3 Sqrt[7])^C[1]) && 
 y == -(((8 - 3 Sqrt[7])^C[1] - (8 + 3 Sqrt[7])^C[1])/(2 Sqrt[7]))

The linear equation has of course also a constant, but this is pointless,isn't it?

In[74]:= Reduce[4 x + 2 y == 28, {x, y}, Integers]
Out[74]= C[1] \[Element] Integers && x == C[1] && y == 14 - 2 C[1]